一、算法定位（一句话定性）

Floyd‑Warshall 是基于动态规划的多源最短路算法。输入一张带权图，直接求出所有点对之间的最短路径。

✅ 优点：代码极简、邻接矩阵实现、无需建复杂邻接表、支持负边权。

❌ 缺点：时间复杂度 O(n³)，仅适合点数 n ≤ 400 的小规模图。

适用场景：普及组 / 提高组图论基础题、传递闭包、负环判断、城市多点互通费用题。

二、核心本质：三维 DP 压成二维

1. 原始 DP 状态定义

设 dist[k][i][j]：只允许使用 前 k 个点 作为中转点时，i 到 j 的最短路。

2. 状态转移方程（核心公式）

dist[k][i][j] = min( dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j] )

含义：

• 要么不经过 k：沿用原来最短路
• 要么经过 k：拆成 i→k + k→j 两段路拼接

3. 空间优化（工程只用这版）

k 只依赖上一层，直接删掉第三维，只用二维邻接矩阵：dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )

三、严格执行顺序：三层循环绝对不能乱

🔴 必须外层 k，中层 i，内层 j

✅ 正确顺序：中转点 k → 起点 i → 终点 j

❌ 顺序写错直接全部答案错误，无法纠错。逻辑：先固定中转站，再批量更新全图所有路径。

四、标准工程模板（可直接 AC 所有题目）

1. 常量与数组定义（防溢出标配）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 405;
// 优选INF：加法不易溢出，安全耐用
const int INF = 0x3f3f3f3f;

// 邻接矩阵存最短路
int dist[N][N];
int n, m;

2. 邻接矩阵标准初始化（必考）

void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }
}

规则：自己到自己距离为 0，不相连初始无穷大。

3. Floyd 核心松弛代码（背下来）

void floyd() {
    // k 必须在最外层：枚举中转点
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 防溢出：只有两段都可达才更新
                if (dist[i][k] < INF && dist[k][j] < INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

五、关键拓展：负权边 + 负环判定

1. 能力边界

Floyd 允许负边权，但不允许负环。有负环则最短路不存在。

2. 负环快速判定（一句话原理）

跑完 Floyd 后，若存在任意点 i 满足 dist[i][i] < 0，说明绕一圈距离变短，即存在负环。

bool has_negative_cycle() {
    for (int i = 1; i <= n; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

六、高频致命坑点（考试必看）

1. 循环顺序写反：i/j/k 乱序 → 全错，无报错。
2. INF 取值乱设：设成 1e9 容易相加溢出爆 int，必须用 0x3f3f3f3f。
3. 不判 INF 直接加：无穷大加无穷大直接溢出负数，评测机直接 WA。
4. 忘记初始化对角线为 0：自己到自己变成无穷大，整张图全乱。
5. 有负环不特判：题目含负环强行求最短路，答案全部错误。

七、Floyd 与 Dijkstra 选型对照表（考场直接用）

维度	Floyd-Warshall	Dijkstra
求解范围	所有点对多源最短路	单源单点出发最短路
时间复杂度	O(n³)	O (m log n) 堆优化
负边权	支持（不可负环）	不支持负边权
代码难度	极简三重循环	邻接表 + 优先队列复杂
适用规模	n ≤ 400	n 上万都能跑

八、适合刷题场景（直接对标洛谷真题）

1. 城市多点互通费用、机场换乘、多站点统一算路费 → 直接 Floyd
2. 传递闭包、判断两点是否可达 → 改一下权值为 0/1 即可
3. 小规模图、不想写邻接表、想快速写最短路 → 无脑 Floyd