Dijkstra算法与弗洛伊德 - 沃肖尔：寻找最​​佳路径上的所有节点对 [英] Dijkstra vs. Floyd-Warshall: Finding optimal route on all node pairs

问题描述

我对Dijkstra算法和弗洛伊德算法读了起来。据我所知，Dijkstra的找到最佳路径从一个节点到所有其他节点和Floyd-沃肖尔找到的所有节点配对的最佳路径。

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算法比弗洛伊德的更有效。

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），其中弗洛伊德的是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!

推荐答案

正如其他人所指出的，弗洛伊德，沃肖尔时间为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.

有一个真正了不起的算法叫做 约翰逊的算法 这是一个轻微的修改到运行Dijkstra的从每个节点，允许该方法来工作，即使该图包含负沿（只要没有任何负面的周期）算法。该算法的工作原理是先在图上运行贝尔曼 - 福特将其转化为无图消极的边缘，然后用Dijkstra算法开始在每个顶点。由于贝尔曼 - 福特运行时间O（MN），整体渐近运行时间仍然是O（MN + N ² log n）的，所以如果m = O（N ² ）（注意，这是n的小-O 的），这种方式是渐进的速度比用弗洛伊德 - 沃肖尔。

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算法背靠一个斐波那契堆。如果您没有斐波那契堆可用，都不愿意投入必要建立72小时，调试和测试的，那么你仍然可以使用二进制堆Dijkstra算法;它只是增加了运行时0（M log n）的，所以这个版本约翰逊的算法运行在O（MN log n）的。这不再总是渐进比弗洛伊德 - 沃肖尔更快，因为如果m =欧米茄（N ² ），那么弗洛伊德-沃肖尔运行在O（N ³ ），而约翰逊的算法为O（N ³ log n）的。然而，对于稀疏图，其中m = O（N ² / log n）的，这个实现约翰逊的算法仍是渐进比弗洛伊德 - 沃肖尔

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

在短期：

• 在同一个斐波那契堆，约翰逊的算法总是渐近至少不如弗洛伊德 - 沃肖尔，尽管它很难code了。
• 使用二元堆，约翰逊的算法的一般的渐近至少不如弗洛伊德 - 沃肖尔，但不是一个好的选择，当大，密集的图形处理。

• 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算法与弗洛伊德 - 沃肖尔：寻找最​​佳路径上的所有节点对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！