Dijkstra vs. Floyd-Warshall:在所有节点对上寻找最佳路线

Question

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

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

Dijkstra的运行时间是O(E + VlogV),其中Floyd是O(V ³).如果Dijkstra失败了,在这种情况下它的运行时间是什么？谢谢!

Answer 1

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

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

这里的一个问题是,假设你有一个由Fibonacci堆支持的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),约翰逊算法的这种实现仍然比Floyd-Warshall渐近地更好.

简而言之:

• 使用Fibonacci堆,Johnson的算法总是渐近渐近至少和Floyd-Warshall一样好,尽管编码起来比较困难.
• 对于二进制堆,Johnson的算法通常渐近至少与Floyd-Warshall一样好,但在处理大而密集的图时不是一个好的选择.

希望这可以帮助!

Answer 2

在所有节点上运行Dijkstra的复杂性将为O(EV + V ² logV).如果E <V ^2,则该复杂度低于O(V ³).

Answer 3

这取决于。对所有节点运行 Dijkstra 会得到O(VE + V^2log V)，而 Floyd 的结果是O(V^3)。如果E = O(V^2)，那么两者在理论上是相同的，而弗洛伊德在实践中更快。如果您这样做E = O(V)，那么对所有节点运行 Dijkstra 在理论上和实践上都更好。

基本上，如果您希望拥有与节点一样多的边，则从所有节点运行 Dijkstra；如果您希望拥有几乎完整的图，则运行 Floyd。