27

“Floyd-Warshall 算法”和“Dijkstra 算法”有什么区别，哪个最适合在图中找到最短路径？

我需要计算网络中所有对之间的最短路径并将结果保存到数组中，如下所示：

**A     B     C     D      E**
A 0     10    15    5     20
B 10     0    5     5     10
C 15     5    0     10    15
D 5      5    10    0     15
E 20     10    15   15    0
4

6 回答 6

24

Dijkstra的算法在图中找到一个节点和每个其他节点之间的最短路径。您将为每个节点运行一次。权重必须为非负数，因此如有必要，您必须首先对图中的值进行归一化。

Floyd-Warshall在一次运行中计算所有节点对之间的最短路径！循环权重必须是非负的，并且图表必须是有向的（您的图表不是）。

Johnson的算法使用 Dijkstra 的算法在一次遍历中找到所有对，并且对于稀疏树更快（参见分析链接）。

于 2009-12-04T13:22:37.433 回答
8

Floyd Warshall 找到所有顶点对之间的路径，但 Dijkstra 只找到从一个顶点到所有其他顶点的路径。

Floyd Warshall 是 O(|V| 3 ) 而 Dikstra 是 O(|E| + |V| log |V|) 但你必须运行它 V 次才能找到所有复杂度为 O(|E * V| + |V 2 | log |V|) 我猜。这意味着重复使用 Dijsktra 可能比 FW 算法更快，我会尝试这两种方法，看看哪种方法在实际情况下最快。

于 2009-12-04T13:11:16.753 回答
5

Dijkstra 只从一个顶点找到最短路径，Floyd-Warshall 在所有顶点之间找到最短路径。

于 2009-12-04T13:13:53.300 回答
2

如果您想找到所有顶点对之间的最短路径，请使用 Floyd-Warshall 算法，因为它的运行时间比 Dijkstra 算法（远）高。

Floyd-Warshall 算法的最坏情况性能为 O(|V| 3 )，而 Dijkstra 算法的最坏情况性能为 O(|E| + |V|log |V|)

于 2009-12-04T13:11:51.200 回答
0

Dijkstra's 主要用于单对最短路径查找，即从一个节点到所有其他节点，其中 Floyd-Warshall 用于所有对最短路径，即所有顶点对之间的最短路径。Floyd-Warshall 算法的最坏情况性能为 O(|V|3)，而 Dijkstra 算法的最差情况性能为 O(|E| + |V|log |V|) 而且 Dijkstra 不能用于负权重（我们同样使用贝尔曼福特）。但是对于 Floyd-Warshall，我们可以使用负权重，但不能使用负循环

于 2012-07-11T08:09:31.137 回答
0

同时，针对单源最短路径问题的更好算法是已知的。一个实际相关的是Torben Hagerup 对 Dijkstra 算法的推导。该算法具有与 Djikstra 相同的最坏情况复杂度，但在平均情况下，预期运行时间与图的大小呈线性关系，这比纯 Dijkstra 快得多。该算法的思想是基于这样的思想，即不需要总是从队列中轮询最小边。可以从队列中轮询一条边，其权重是1+k最小边权重的倍，其中k一些数字更大0。即使选择了这样一条边，算法仍然会找到最短路径。

于 2012-10-17T05:34:07.940 回答