最好的最短路径算法

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计算一次运行中所有节点对之间的最短路径!循环权重必须是非负的,并且必须指向图形(您的图表不是).

约翰逊的算法使用Dijkstra算法在一次通过中找到所有对,并且对于稀疏树更快(参见分析链接).

Answer 2

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

Floyd Warshall是O(| V | ³)而Dikstra是O(| E | + | V | log | V |)但是你必须运行V次以找到所有给出复杂度为O的对(| E*V | + | V ² | log | V |)我猜.这意味着重复使用Dijsktra可能比FW算法更快,我会尝试两种方法,看看在实际情况下哪一种最快.

Answer 3

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