la Gavoille等人是否有一种带距离标记的最短路径算法的开源实现？

Question

如果允许|V|在图形上预先计算线性数据量,那么有一系列算法对图中的最短路径具有次线性查询时间.

1. Gavoille等.图中的距离标记.
2. 科恩等人.通过2跳标签进行可达性和距离查询
3. 亚伯拉罕,戈德堡等人.最短路径的分层中心Labellings

其中一些在Bing Maps中用于极快的最短路径计算.

基本思想是为每个顶点前向标签L_f(v)和后向标签预先计算,这些标签L_b(v)构成了一个封面属性.每个标签是一对顶点和它的距离,例如L_f(v) = { (u, dist(v, u)) }和L_r(v) = { (u, dist(u, v)) }.并且cover属性声明对于任何顶点s和t'Union L_f(s)' L_r(t)在从s到t的最短路径上包含至少一个顶点.

是否有其中一种算法(C++,C#,F#,D,Go,Java)的开源实现？

Answer 1

我还没有找到任何实现这些算法的代码，但您可以查看卡尔斯鲁厄主页，在那里您可以找到收缩层次结构的代码，它构成了（原始）中心标签的基础。您可以使用它来创建您自己的 HL 实现，但您应该知道他们为此申请了专利。