Dijkstra vs. Floyd-Warshall:在所有节点对上寻找最佳路由 [英] Dijkstra vs. Floyd-Warshall: Finding optimal route on all node pairs

问题描述

我正在阅读 Dijkstra 算法和 Floyd-Warshall 算法.我知道 Dijkstra 找到了从一个节点到所有其他节点的最佳路线，而 Floyd-Warshall 找到了所有节点配对的最佳路线.

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.

我的问题是，如果我在每个节点上运行 Dijkstra 的算法以找到所有配对之间的最佳路线，那么它是否会比 Floyd 的算法更有效.

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 的运行时间为 O(E + VlogV)，其中 Floyd 的运行时间为 O(V³).如果 Dijkstra 失败，在这种情况下它的运行时间是多少?谢谢！

Dijkstra's runtime is O(E + VlogV) where Floyd's is O(V³). If Dijkstra's fails, what would its runtime be in this case? Thanks!

推荐答案

正如其他人所指出的，Floyd-Warshall 运行时间为 O(n³) 并从每个节点运行 Dijkstra 搜索到假设您使用斐波那契堆来支持 Dijkstra 的实现，每个其他节点需要 O(mn + n² log n).但是，您不能总是在任意图上安全地运行 Dijkstra 算法，因为 Dijkstra 算法不适用于负边权重.

As others have pointed out, Floyd-Warshall runs in time O(n³) 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 + n² 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.

有一种真正出色的算法，称为Johnson 算法这是对从每个节点运行 Dijkstra 算法的轻微修改，即使图形包含负边(只要没有任何负循环)，也允许该方法工作.该算法首先在图上运行 Bellman-Ford 以对其进行转换到没有负边的图，然后使用 Dijkstra 算法从每个顶点开始.因为 Bellman-Ford 在时间 O(mn) 中运行，整体渐近运行时间仍然是 O(mn + n² log n)，所以如果 m = o(n²)(注意这是 n 的 little-o)，这种方法比使用 Floyd-Warshall 渐进快.

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 + n² log n), so if m = o(n²) (note that this is little-o of n), this approach is asymptotically faster than using Floyd-Warshall.

这里的一个问题是，这假设您拥有由斐波那契堆支持的 Dijkstra 算法.如果您没有可用的 Fibonacci 堆，并且不愿意投入 72 小时来构建、调试和测试一个堆，那么您仍然可以为 Dijkstra 算法使用二进制堆；它只是将运行时间增加到 O(m log n)，所以这个版本的 Johnson 算法以 O(mn log n) 运行.这不再总是比 Floyd-Warshall 渐进快，因为如果 m = Ω(n²) 那么 Floyd-Warshall 在 O(n³) 中运行，而 Johnson 算法在 O(n³ log n) 中运行.然而，对于稀疏图，其中 m = o(n²/log n)，Johnson 算法的这种实现仍然渐近优于 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 = Ω(n²) then Floyd-Warshall runs in O(n³) while Johnson's algorithm runs in O(n³ log n). However, for sparse graphs, where m = o(n² / log n), this implementation of Johnson's algorithm is still asymptotically better than Floyd-Warshall

简而言之:

• 使用斐波那契堆，约翰逊的算法总是渐近渐近，至少与 Floyd-Warshall 一样好，尽管编码更难.
• 对于二叉堆，Johnson 的算法通常渐近地至少与 Floyd-Warshall 一样好，但在处理大而密集的图时不是一个好的选择.

• With a Fibonacci heap, Johnson's algorithm is always asymptotically at least as good as Floyd-Warshall, though it's harder to code up.
• With a binary heap, Johnson's algorithm is usually asymptotically at least as good as Floyd-Warshall, but is not a good option when dealing with large, dense graphs.

希望这有帮助！

这篇关于Dijkstra vs. Floyd-Warshall:在所有节点对上寻找最佳路由的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！