算法笔记：Floyd-Warshall算法

哦哦，哦哦哦！

好看的

算法作用

在一张有N个节点的非负权值图中，以O(N^3)的复杂度寻找每两个节点之间最短路径的长度的算法。

准备工作

要执行Floyd-Warshall算法，我们需要如下元素：

• 一张不存在负权环的，有N个节点的图G。
• 一个N * N大小的邻接矩阵M，用于表示每两个节点之间的最短距离。

算法步骤

0. 将M中的所有值初始化为+INF.
1. 枚举G中的所有边<u, v, w>（从u到v的，权值为w的边）；将M[u][v]设为w。
2. 从1到N枚举中间节点K, 对于每一个K：
   从1到N枚举源节点S与目标节点D。对于每一个<S, D, K>，有：
   M[S][D] = min(M[S][D], M[S][K] + M[K][D]).
3. 当该三重循环结束，M[i][j]即为该有向图G中节点i到节点j的最短路径。

正确性证明

正确性证明（英文）

说明

如果一张图中存在负权环，那么该图中两点之间的最短路径不存在（可以无限次经过负权环）。