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

Question

如果您被允许预先计算图上 |V| 数据量的线性，那么有一系列算法对图中的最短路径具有亚线性查询时间。

1. Gavoille 等人。图表中的距离标记。
2. 科恩等人。通过 2 跳标签进行可达性和距离查询
3. 亚伯拉罕、戈德堡等人。 Hierarchical Hub Labellings for Shortest Paths

其中一些用于 Bing Maps用于极快的最短路线计算。

基本思想是预先计算每个顶点的前向标签L_f(v)和后向标签L_b(v)，它们构成了一个覆盖属性。每个标签都是一对顶点和到它的距离，例如L_f(v) = { (u, dist(v, u)) } 和 L_r(v) = { (u, dist(u, v)) }。 cover property 断言对于任何顶点 s 和 t L_f(s) 'Union' L_r(t) 至少包含一个顶点从 s 到 t 的最短路径。

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

Answer 1

我还没有找到任何实现这些算法的代码，但您可以查看 the Karlsruhe homepage您可以在其中找到构成(原始)Hub 标签基础的 Contraction Hierarchies 的代码。您可以使用它来创建您自己的 HL 实现，但您应该知道他们提交了 patent