最短路径：Floyd-Warshall 算法动画

每一轮固定一个中转点 k，检查从 i 到 j 是否可以借助 k 变短。图和矩阵同步高亮，重点看距离表如何被更新。

控制

慢 快
当前步 0 / 0
中转点 k -
本步结果 初始化

当前判断

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

初始矩阵只记录直接边，自己到自己为 0，没有直接边记为 ∞。

图与距离矩阵

只看更新步骤
无向带权图 边权为路径长度
3 2 6 2 1 4 3 6 A B C D E F
起点 i 中转 k 终点 j
距离矩阵 d[i][j] 初始化

讲解要点

  • k 的含义：第 k 轮结束后，允许经过的中转点范围扩大了一步。
  • 更新条件：如果 d[i][k] + d[k][j] 比原来的 d[i][j] 小，就替换为更短路径。
  • 适用场景：求任意两点之间的最短路，图规模不大时尤其方便。
  • 复杂度：三重循环，时间复杂度 O(n^3)，空间复杂度通常为 O(n^2)。

C++ 核心代码

const int INF = 0x3f3f3f3f;

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][k] != INF && d[k][j] != INF) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}