c++ - 无向加权稀疏图的所有对最短路径长度

Question

寻找无向加权稀疏图的所有对最短路径长度的最佳算法是什么？具体来说，权重是节点之间的距离(因此是正数)。请注意，我只需要路径长度(即不是路径本身)。我的图是稀疏的，因此它存储为邻接表。

我找到了 Dijkstra、Floyd-Warshall、Johnson 等人，但他们似乎都不是最适合我的目的。在 Dijkstra 的情况下，您在所有顶点上运行单一源版本，Floyd-Warshall 用于密集图，Johnson 用于有向图。

我正在专门寻找 C++ 中的实现。

Answer 1

Johnson's algorithm似乎最适合稀疏图(如果 |V| > |E| 它归结为 O(V^2logV)，而不是 O(V^3) 与 FW)。但是，由于 Johnson 算法的第一步是使权重非负(您不需要)，因此您可能只运行第二步，正如您正确指出的那样，这实际上只是来自每个节点的 Dijkstra。如 here, on the last slide 所述，那应该只需要 O(VElogV) .我不确定我能否证明它是最佳解决方案，但如果有更好的解决方案(用于寻找非负权重的最短路径)- 我希望 Johnsons 算法在重写权重后使用它。

它适用于有向图的事实不应该打扰你 - 你可以将无向图转换为有向图，只需将每个无向边与 2 个有向边来回转换(使用简单的 O(E) 时间) .也就是说 - 除非您有空间限制。