约定
为了方便叙述，这里先给出下文将会用到的一些记号的含义。
- n 为图上点的数目，m 为图上边的数目；
- s 为最短路的源点；
- D(u) 为 s 点到 u 点的 实际 最短路长度；
- dis(u) 为 s 点到 u 点的 估计 最短路长度。任何时候都有 dis(u) \ge D(u)。特别地，当最短路算法终止时，应有 D(u) = dis(u)。
- w(u, v) 为 (u, v) 这一条边的边权。
Floyd
特点
用来求任意两个节点之间的最短路
复杂度高( O(n^3) ) 大约只能处理节点数量在 200 左右的图。
适用于任何图，不管有环无环，有边权还是无边权。但是两个节点之间必须有最短路（连通图）（负环除外）
实现
类似动态规划， 定义数组 f[k][x][y] 表示只允许经过节点 1-k 时节点 x 和节点 y 的最短路径。（注意：x, y 不一定在子图之内 ）
很显然，f[n][x][y] 就是结点 x 到结点 y 的最短路长度。
接下来考虑如何求出 f 数组的值：
- 对于
f[0][x][y]来说，值为0或 +\infty 或 w(x,y) （两点重合时为0或两点无直接相连的边为 +\infty 两点有直接相连的边时为 w(x,y) ） - 对于
f[k][x][y]来说f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])（在 x 和 y 之间插入了点 k ，f[k - 1][x][y]是不经过 k 的最短路f[k-1][x][k]+f[k-1][k][y]是经过了点 k 的最短路）
显然这两个都是对的，但是空间复杂度也使 O(n^3)
for (k = 1; k <= n; k++)
{
for (x = 1; x <= n; x++)
{
for (y = 1; y <= n; y++)
{
f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
}
}
}
优化:
可以去掉第一维 k
证明：
当我们转移到 f[k][x][y] 时涉及的元素总是来自于 涉及的元素总是来自 f[k-1] 数组的第 k 行和第 k 列 。
更新f[k][x][k] 和 f[k][k][y]时的数据总是不会发生更新。
根据公式 f[k][k][y] = min(f[k-1][k][y], f[k-1][k][k]+f[k-1][k][y]) 来说 f[k-1][k][k] 为 0，因此这个值总是 f[k-1][k][y] ，对于 f[k][x][k] 的证明类似。
for (k = 1; k <= n; k++)
{
for (x = 1; x <= n; x++)
{
for (y = 1; y <= n; y++)
{
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
