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

Question

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

1. Gavoille 等人。图中的距离标记。
2. 科恩等人。通过 2 跳标签的可达性和距离查询
3. 亚伯拉罕，戈德堡等人。最短路径的分层集线器标签

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

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

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

Answer 1

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