最好的最短路径算法

Question

“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

Answer 1

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

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

Johnson 的算法使用 Dijkstra 算法一次查找所有对，对于稀疏树来说速度更快（请参阅分析链接）。

Answer 2

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

Floyd Warshall 的复杂度为 O(|V|

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

Answer 3

Dijkstra 仅从

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

Answer 4

如果您想找到

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

Floyd-Warshall 算法的最坏情况性能为 O(|V|

3^{)，而 Dijkstra 算法的最坏情况性能为 O(|E| + |V|log |V|)}

Answer 5

与此同时，针对单源最短路径问题的更好算法是已知的。一个实际相关的算法是 Torben Hagerup 的

Dijkstra 算法的推导。该算法具有与 Djikstra 相同的最坏情况复杂度，但在平均情况下，预期运行时间与图的大小呈线性关系，这比纯 Dijkstra 快得多。该算法的思想基于这样的思想：不需要总是从队列中轮询最小边。可以从队列中轮询一条边，其权重是最小边权重的1+k

倍，其中

k

是大于

0

的某个数字。即使选择了这样的边，算法仍然会找到最短路径。

Answer 6

Dijkstra 主要用于单对最短路径查找，即从一个节点到所有其他节点，而 Floyd-Warshall 则用于全对最短路径，即所有顶点对之间的最短路径。 Floyd-Warshall 算法的最坏情况性能为 O(|V|3)，而 Dijkstra 算法的最坏情况性能为 O(|E| + |V|log |V|) 此外，Dijkstra 不能用于负权重（我们使用 Bellmann Ford 进行同样的操作）。但对于 Floyd-Warshall，我们可以使用负权重，但不能使用负循环

Answer 7

算法时间复杂度（大O）空间复杂度（大O）直接图还是非直接图？处理循环图？处理负边权重？什么时候使用？Dijkstra 算法(E+V)LogVV两者没有没有获取从单个源到所有顶点的最短路径贝尔曼-福特算法VEV两者不适用于负体重周期是的获取从单个源到所有顶点的最短路径拓扑排序算法V+EV直接没有是的获取从单个源到所有顶点的最短路径Floyd-Warshall 算法V^3V^2两者不适用于负体重周期是的获取从所有顶点到所有顶点的最短路径