Floyd适用于任何没有负环的图 (即一定有最短路)
定义数组 f[k][x][y] 表达只允许经过最大是k的节点, x 到 y 的最短路 (即只包含 [1, k]的子图中 x 到 y 的最短路，当然x, y 并不一定在在这个子图内)。
通过以上定义，我们可以一点一点添加新的节点，得到新的子图。新的子图与原子图的关系是这个新加的节点，设新的点为k + 1，那么x到y的最短路 只可能是 f[k+1][x][y] = min(f[k][x][y], f[k][x][k+1] + f[k][k+1][y])。 这样我们就得到了:
f[0][x][x] = 0f[0][x][y] = w[x][y] if [x, y] exists else +inff[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y])时间复杂度O(n^3)