Dijkstra 与 Floyd-Warshall：在所有节点对上寻找最佳路线
我正在阅读 Dijkstra 算法和 Floyd-Warshall 算法。据我所知，Dijkstra 找到了从一个节点到所有其他节点的最佳路线，而 Floyd-Warshall 找到了所有节点配对的最佳路线。
我的问题是，如果我在每个节点上运行 Dijkstra 算法以找到所有配对之间的最佳路线，它会比 Floyd 算法更有效吗？
Dijkstra 的运行时间是 O(E + VlogV)，而 Floyd 的运行时间是 O(V3)。如果 Dijkstra 失败了，在这种情况下它的运行时间是多少？谢谢！
I am reading up on Dijkstra's algorithm and the Floyd-Warshall algorithm. I understand that Dijkstra's finds the optimal route from one node to all other nodes and Floyd-Warshall finds the optimal route for all node pairings.
My question is would Dijkstra's algorithm be more efficient than Floyd's if I run it on every single node in order to find the optimal route between all pairings.
Dijkstra's runtime is O(E + VlogV) where Floyd's is O(V3). If Dijkstra's fails, what would its runtime be in this case? Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
正如其他人指出的那样，Floyd-Warshall 在时间 O(n3) 中运行，并从每个节点到每个其他节点运行 Dijkstra 搜索，假设您使用 Fibonacci 堆来支持 Dijkstra 的实现，需要 O(mn + n2 log n)。然而，您不能总是在任意图上安全地运行 Dijkstra 算法，因为 Dijkstra 算法不适用于负边权重。
有一个真正非凡的算法，称为约翰逊算法，它是对从每个节点运行 Dijkstra 算法进行轻微修改，即使图形包含负边（只要没有任何负循环），该方法也可以工作。该算法的工作原理是首先在图表上运行 Bellman-Ford 来对其进行转换到一个没有负边的图，然后从每个顶点开始使用 Dijkstra 算法。由于 Bellman-Ford 运行时间为 O(mn)，因此总体渐近运行时间仍然为 O(mn + n2 log n)，因此如果 m = o(n2 ）（请注意，这是 n 的 little-o），这种方法比使用 Floyd-Warshall 渐近更快。
这里的一个问题是，这假设您有由斐波那契堆支持的 Dijkstra 算法。如果您没有可用的斐波那契堆，并且不愿意投入必要的 72 小时来构建、调试和测试斐波那契堆，那么您仍然可以对 Dijkstra 算法使用二进制堆；它只是将运行时间增加到 O(m log n)，因此这个版本的 Johnson 算法的运行时间为 O(mn log n)。这不再总是比 Floyd-Warshall 渐近更快，因为如果 m = Ω(n2)，那么 Floyd-Warshall 的运行时间为 O(n3)，而 Johnson 的算法运行时间复杂度为 O(n3 log n)。然而，对于稀疏图，其中 m = o(n2 / log n)，约翰逊算法的这种实现仍然渐近优于 Floyd-Warshall
简而言之：
希望这有帮助！
As others have pointed out, Floyd-Warshall runs in time O(n3) and running a Dijkstra's search from each node to each other node, assuming you're using a Fibonacci heap to back your Dijkstra's implementation, takes O(mn + n2 log n). However, you cannot always safely run Dijkstra's on an arbitrary graph because Dijkstra's algorithm does not work with negative edge weights.
There is a truly remarkable algorithm called Johnson's algorithm that is a slight modification to running Dijkstra's algorithm from each node that allows that approach to work even if the graph contains negative edges (as long as there aren't any negative cycles). The algorithm works by first running Bellman-Ford on the graph to transform it to a graph with no negative edges, then using Dijkstra's algorithm starting at each vertex. Because Bellman-Ford runs in time O(mn), the overall asymptotic runtime is still O(mn + n2 log n), so if m = o(n2) (note that this is little-o of n), this approach is asymptotically faster than using Floyd-Warshall.
The one catch here is that this assumes that you have Dijkstra's algorithm backed by a Fibonacci heap. If you don't have Fibonacci heap available and aren't willing to put in the 72 hours necessary to build, debug, and test one, then you can still use a binary heap for Dijkstra's algorithm; it just increases the runtime to O(m log n), so this version of Johnson's algorithm runs in O(mn log n). This is no longer always asymptotically faster than Floyd-Warshall, because if m = Ω(n2) then Floyd-Warshall runs in O(n3) while Johnson's algorithm runs in O(n3 log n). However, for sparse graphs, where m = o(n2 / log n), this implementation of Johnson's algorithm is still asymptotically better than Floyd-Warshall
In short:
Hope this helps!
在所有节点上运行 Dijkstra 的复杂度将为 O(EV + V2logV)。此复杂度低于 O(V3) iff E V2。
The complexity for running Dijkstra on all nodes will be O(EV + V2logV). This complexity is lower than O(V3) iff E < V2.
这取决于。对所有节点运行 Dijkstra 的结果是
O(VE + V^2log V)，而 Floyd 的结果是O(V^3)。如果E = O(V^2)，那么两者在理论上是相同的，而 Floyd 在实践中更快。如果您E = O(V)，那么对所有节点运行 Dijkstra 在理论上和实践中都更好。基本上，如果您希望拥有与节点一样多的边，则从所有节点运行 Dijkstra；如果您希望拥有几乎完整的图，则运行 Floyd。
It depends. Running Dijkstra for all nodes gives you
O(VE + V^2log V), while Floyd's isO(V^3). IfE = O(V^2), then the two are theoretically identical, with Floyd being faster in practice. If youE = O(V), then running Dijkstra for all nodes if better both in theory and in practice.Basically, run Dijkstra from all nodes if you expect to have about as many edges as you have nodes, and run Floyd if you expect to have almost complete graphs.
对于所有对最短路径，几乎没有 Floyd-Warshall 比 Dijkstra 更快（通常！！）
No practically Floyd-Warshall is faster than Dijkstra's for all pair shortest path (generally!!)