algorithm - 最好的最短路径算法

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 算法一次性找到所有对，并且对于稀疏树更快(分析见链接)。