最短路径的实现算法（二）：弗洛伊德算法（Floyd）

实现原理

弗洛伊德算法的基本思想如下：

从任意节点 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)，所以这种情况下使用迪杰斯特拉算法更合适。