“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
最佳答案
Dijkstra的算法找到一个节点和图中每个其他节点之间的最短路径。您将为每个节点运行一次。权重必须是非负数,因此如有必要,您必须先对图中的值进行归一化。
Floyd-Warshall在单次运行中计算所有节点对之间的最短路线!循环权重必须是非负数,并且图表必须是有向(您的图表不是)。
Johnson的算法使用 Dijkstra 算法一次性找到所有对,并且对于稀疏树更快(分析见链接)。
关于algorithm - 最好的最短路径算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1846836/