一、算法定位（一句话定性）
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; }六、高频致命坑点（考试必看）
- 循环顺序写反：i/j/k 乱序 → 全错，无报错。
- INF 取值乱设：设成 1e9 容易相加溢出爆 int，必须用 0x3f3f3f3f。
- 不判 INF 直接加：无穷大加无穷大直接溢出负数，评测机直接 WA。
- 忘记初始化对角线为 0：自己到自己变成无穷大，整张图全乱。
- 有负环不特判：题目含负环强行求最短路，答案全部错误。
七、Floyd 与 Dijkstra 选型对照表（考场直接用）
| 维度 | Floyd-Warshall | Dijkstra |
|---|---|---|
| 求解范围 | 所有点对多源最短路 | 单源单点出发最短路 |
| 时间复杂度 | O(n³) | O (m log n) 堆优化 |
| 负边权 | 支持（不可负环） | 不支持负边权 |
| 代码难度 | 极简三重循环 | 邻接表 + 优先队列复杂 |
| 适用规模 | n ≤ 400 | n 上万都能跑 |
八、适合刷题场景（直接对标洛谷真题）
- 城市多点互通费用、机场换乘、多站点统一算路费 → 直接 Floyd
- 传递闭包、判断两点是否可达 → 改一下权值为 0/1 即可
- 小规模图、不想写邻接表、想快速写最短路 → 无脑 Floyd
