Floyd 算法

$d_{ij}^{(k)}$ 代表从结点 i 到 j 而中间结点仅仅属于 1 到 k 的 k 个结点的所有通路之间的最短通路长度

若已知 $D^{(k-1)}=d_{ij}^{(k-1)}$

状态转移方程：

$$D^{(k)}=d_{ij}^{(k)}=min\{d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k+1)}\}$$

初始值

f[0][x][y]：x 与 y 的边权

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]);
} } }

同样可以标记来源来求出最小通路