为无向加权稀疏图找到所有对最短路径长度的最佳算法是什么？具体来说，权重是节点之间的距离（因此是正的）。请注意，我只需要路径长度（即不需要路径本身）。我的图是稀疏的，所以它被存储为邻接列表。
我找到了 Dijkstra、Floyd-Warshall、Johnson 等，但它们似乎都不适合我的目的。对于 Dijkstra，您在所有顶点上运行单一源版本，Floyd-Warshall 用于密集图，而 Johnson 用于有向图。
我正在专门寻找 C++ 中的实现。
问问题
1455 次
3 回答
1
Johnson 的算法似乎最适合稀疏图（如果 |V| > |E| 它归结为 O(V^2logV)，而不是 FW 的 O(V^3)）。但是，由于约翰逊的算法将第一步用于使权重为非负（您不需要），因此您可以只运行您正确指出的第二步，这实际上只是来自每个节点的 Dijkstra。如最后一张幻灯片中所述，这应该只需要 O(VElogV) 。我不确定我能否证明它是最好的解决方案，但是否有更好的解决方案（用于寻找非负权重的最短路径） - 我希望 Johnsons 算法在重写权重后使用它。
它适用于有向图的事实不应该打扰您 - 您可以将无向图转换为有向图，只需将每个无向边与 2 条有向边来回转换（使用简单的 O(E) 时间）。那就是 - 除非你有空间限制。
于 2013-10-15T14:13:50.370 回答
0
由于它是一个无向加权稀疏图，它与道路网络非常相似，所以我不认为（根据经验）有比 Dijkstra 更好的算法。看看双向 dijkstra，如果你有足够的 RAM，你可以缓存每个节点的最短路径树 (SPT)，然后在点 i 的 SPT 与点 j 的 SPT 之间进行“匹配”，其中 i != j.
于 2013-10-21T07:14:28.870 回答
0
我还没有测试过，但 2013 年的这篇论文声称以 47 倍的优势击败了 Dijkstra：
Urakov AR，Timeryaev TV：高维稀疏图的全对最短路径算法：
与 Dijkstra 算法相比，所提出的算法将 APSP 的求解速度平均提高了 47 倍。对于每个和所有测试图，该算法都比 Dijkstra 算法快（最小加速是 34 倍）。在测试过程中，顶点度数增加到最大 17。这意味着在拆卸过程中顶点移除的复杂性仅略有增加。
于 2018-06-18T09:26:11.013 回答