Floyd-Warshall 全源最短路算法

📖 算法原理：三重循环动态规划

Floyd 算法是解决全源最短路径问题（求解图中任意两点间的最短路径）的经典动态规划算法，能够处理负权边（但不能处理负权回路）。

📐 核心状态转移方程

我们用 dp[i][j] 表示从 $i$ 到 $j$ 的当前已知最短距离。当考虑引入中介节点 $k$ 时：

$$\color{cyan} dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k][j])$$

其物理意义极其直观：从 $i$ 直达 $j$ 的距离，与“先从 $i$ 到中转点 $k$，再从 $k$ 到 $j$”的距离之和，二者取较小值。

演示速度：

点击"开始演示"或"单步执行"观察中介点 K（橙色）的测试，以及矩阵单元格的动态更新过程。

🕸️ 4 节点有向加权图

📊 dp[4][4] 全源最短路矩阵

i \ j	1	2	3	4

当前中介点 K-

当前起点 I-

当前终点 J-

三重迭代步数0 / 64

void floyd() {
    // dp[i][j] 初始填充为邻接矩阵的权值
    for (int k = 1; k <= n; k++) { // 1. 中介点放在最外层循环！
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 2. 状态转移方程：测试经过中介点 k 是否更优
                if (dp[i][k] != INF && dp[k][j] != INF) {
                    if (dp[i][j] > dp[i][k] + dp[k][j]) {
                        dp[i][j] = dp[i][k] + dp[k][j]; // 松弛更新
                    }
                }
            }
        }
    }
}

📋 矩阵更新历史步骤日志