实现原理
弗洛伊德算法的基本思想如下:
从任意节点 A 到任意节点 B 的最短路径不外乎两种可能,一种是直接从 A 到 B,一种是从 A 经过若干个节点到 B,所以,我们假设 dist(A,B) 为节点 A 到节点 B 的最短路径的距离,对于每一个节点 K,我们检查 dist(A,K) + dist(K,B) < dist(A,B) 是否成立,如果成立,证明从 A 到 K 再到 B 的路径比 A 直接到 B 的路径短,我们便设置 dist(A,B) = dist(A,K) + dist(K,B),这样一来,当我们遍历完所有节点 K,dist(A,B) 中记录的便是 A 到 B 的最短路径的距离。
算法复杂度
弗洛伊德算法实现包含三层循环,对应的算法时间复杂度也是 O(n3),但是实现起来更简单,适用于需要计算所有顶点间的最短路径这种场景;迪杰斯特拉还可以计算指定顶点到其他顶点的最短路径,时间复杂度只有 O(n2),所以这种情况下使用迪杰斯特拉算法更合适。
评论区