我需要找到图 G 中所有对之间的最短路径。我正在使用 Floyd–Warshall 算法来计算解决方案。
鉴于这些关于 G 的事实，我需要知道是否有更好的选择来找到所有最短路径:
G是一个无向图。- 顶点数和边数相同。
- 所有的边权重都是正的。
鉴于这些事实，是否有比 Floyd-Warshall 更好的解决方案？
最佳答案
对稀疏图的 Dijkstra 最短路径算法进行了修改，该算法运行速度非常快，并揭示了对数线性(接近线性)渐近行为。您需要从 N 个顶点进行 N 次搜索，从而提供比 O(N^3) Floyd–Warshall 算法更好的 O(N^2*LogN) 渐近时间。
可能你的图有特殊的拓扑结构，允许更有效的方法......
C++ code with Russian description (可能由谷歌浏览器翻译)
我有网格图的 delphi 实现 here .
关于algorithm - 优化搜索具有 N 个顶点和 N 条边的图中的所有最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31397920/