Floyd 算法学习笔记
核心思想
Floyd 算法基于 DP，只要记住 k 点在最外层 就可以。
就是一个搭桥思想：看 \(u \to v\) 是否可以被一个点 \(k\)，使得 \(u \to k + k \to v\) "抄小路"。
核心代码真的很短：
for(int k = 1; k <= n; k++)for(int u = 1; u <= n; u++)for(int v = 1; v <= n; v++)f[u][v] = min(f[u][v], f[u][k] + f[k][v]);
实质上是 DP：
其中 \(f[k][u][v]\) 表示从 \(u\) 到 \(v\) 的路径中，只允许经过编号 \(\le k\) 的中间节点时，最短路径长度。
滚动掉 \(k\) 这一维，就成了现在这个样子。
如果仿照 Dijkstra，需要后续操作，就写成：
if(f[u][v] > f[u][k] + f[k][v])
{f[u][v] = f[u][k] + f[k][v];// 后续操作...
}
变式一：传递闭包
🟡 B3611 【模板】传递闭包
链接：B3611 传递闭包
传递闭包的意思是：任意 \(u\) 能否到达 \(v\)。
只需要把 min 换成 | 和 & 就行：
\(u \to v\) 就看 \(u \to v\) 本身，和 \(u \to k\) 且 \(k \to v\) 能否同时畅通。
代码：
for(int k = 1; k <= n; k++)for(int u = 1; u <= n; u++)for(int v = 1; v <= n; v++)f[u][v] = f[u][v] | (f[u][k] & f[k][v]);
变式二：实时枚举（动态加点）
🟢 P1119 灾后重建
链接：P1119 灾后重建
题目：每个点在不同的时刻重建完成，询问 \(x \to y\) 在某个时间点的最短路和可达性。
这道题保证了询问时间升序，我们可以边读入边做题，把刚刚重建好的村庄当作 \(k\)（中转点）去松弛，这样就能保证所有用到的点已经重建完毕。
核心代码：
// 把所有重建时间 <= time 的村庄加入中转集合
// 相当于 Floyd 的 k 循环逐步展开
while(now < n && t[now] <= time)
{// 把 now 作为中转点，松弛所有点对for(int i = 0; i < n; i++) // 题目采用 0-basedfor(int j = 0; j < n; j++)f[i][j] = min(f[i][j], f[i][now] + f[now][j]);now++; // 指针后移，继续处理下一个村庄
}
要点：
- Floyd 的 \(k\) 循环是可拆解的
- 相当于定义了一个函数
relax(k)，每次只松弛一个中转点 - 题目保证了 \(t[0] \le t[1] \le \dots \le t[n-1]\)，所以可以用指针
now顺序推进
变式三：最小环
🟢 P6175 无向图的最小环
链接：P6175 最小环
最小环不仅要至少三个点，还必须保证这个环不能经过重复的点。所以不可以说 \(f[i][j] + f[i][k] + f[k][j]\) 是个环。
这题目也体现了 Floyd 的零件性：我们把 \(k\) 放上面，先链接 \(k-1\) 的点连环，再推第 \(k\) 个点状态。
核心代码：
for(int k = 1; k <= n; k++)
{// 先看 k-1 范围内的路径连环for(int i = 1; i <= k - 1; i++)for(int j = i + 1; j <= k - 1; j++) // 枚举 i < j < kans = min(ans, f[i][j] + e[i][k] + e[k][j]);// 为什么要这样子做呢？为了保证简单的环不能重复经过节点// 如果采用 f[i][j] + f[i][k] + f[k][j]，i=>k 与 k=>j 可能反复经过某一个节点// 值更小就会影响答案// 再去递推第 k 个节点的 Floyd 状态for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
为什么用 e[i][k] 而不是 f[i][k]？
因为要保证 \(k\) 是环中编号最大的点，i → k 和 k → j 必须是直接边，不能经过其他点中转。否则 \(k\) 就不是"最大编号"了，环会被重复计算。
而且,如果用 \(f[i][k]\),可能会使得经过点重复,值反而更小,影响更新.
关键点：
- 先找环，再更新最短路（顺序不能反）
e[i][k]是原始边权，不是最短路- 枚举时保证 \(i < j < k\)，避免重复
变式四：枚举优化（传送门）
🟢 P6464 [传智杯 #2] 传送门
链接：P6464 传送门
题目：在哪两个点之间建传送门（边权为 0）可以使得所有点对距离之和最小？
这道题同样是有一次机会 \(w = 0\)（与 P4568 对比），但这里是新建一条边，而非把已有的边变成 0。
传送门 \((i, j)\) 只会影响经过 \(i\) 或 \(j\) 的路径：
- \(x \to i \to j \to y\)
- \(x \to j \to i \to y\)
其他路径如果不经过传送门，不会受到影响。
核心代码：
// 枚举传送门每一条可能
for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++) // 升序，节省一半时间{// dis 重置为 Floyd 的状态for(int x = 1; x <= n; x++)for(int y = 1; y <= n; y++)dis[x][y] = f[x][y];// 传送门两边设为 0dis[i][j] = dis[j][i] = 0;// 以 i 为中转点进行更新for(int x = 1; x <= n; x++)for(int y = 1; y <= n; y++)dis[x][y] = min(dis[x][y], dis[x][i] + dis[i][y]);// 以 j 为中转点进行更新for(int x = 1; x <= n; x++)for(int y = 1; y <= n; y++)dis[x][y] = min(dis[x][y], dis[x][j] + dis[j][y]);// 统计答案，取 minsum = 0;for(int x = 1; x <= n; x++)for(int y = x + 1; y <= n; y++)sum += dis[x][y];ans = min(ans, sum);}
为什么不用再跑完整的 Floyd？
因为传送门只影响经过 \(i\) 或 \(j\) 的路径，用 \(i\) 和 \(j\) 分别做一次中转点松弛，就相当于把传送门的影响传播到了整个图。其他点做中转点，路径不会经过传送门，所以不需要。
变式五：路径打印
🟡 P1347 排序
链接：P1347 排序
这道题如果用传递闭包做，那么 \(f[i][i] = 1\) 就是环（正常 Floyd 判负环是 \(f[i][i] < 0\)）。
当所有点两两之间最短路确定，就代表所有点的大小关系可以确定。
路径打印代码：
int pre[N][N]; // pre[i][j] 表示 i→j 最短路径上 j 的前驱// 初始化：默认从 i 直接到 j
for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)pre[i][j] = i;// Floyd 传递闭包中更新 pre
if(f[i][k] && f[k][j])
{f[i][j] = 1;pre[i][j] = pre[k][j]; // j 的前驱变成 k→j 路径上的前驱
}// 递归打印路径
void print_path(int u, int v)
{if(u == v) { cout << itoc(u); return; }print_path(u, pre[u][v]); // 先打印前半段cout << itoc(v); // 再打印当前点
}
打印原理：
假设路径是 A → B → C → D，则 pre[A][D] = C，pre[A][C] = B，pre[A][B] = A。
print_path(A, D) 的执行过程：
print_path(A, pre[A][D])→print_path(A, C)print_path(A, pre[A][C])→print_path(A, B)print_path(A, pre[A][B])→print_path(A, A)→ 输出A- 回溯输出
B、C、D
最终输出：ABCD ✅
关键点：
- 传递闭包中，\(f[i][i] = 1\) 表示有环（矛盾）
- 判断全序：所有 \(i \ne j\) 都满足 \(f[i][j]\) 或 \(f[j][i]\)
- 路径打印用递归回溯，代码最简洁
总结：Floyd 变式一览
| 变式 | 核心改动 | 代表题目 |
|---|---|---|
| 传递闭包 | min → |，+ → & |
B3611 |
| 动态加点 | 把\(k\) 循环拆开，按时间推进 | P1119 |
| 最小环 | 在 Floyd 更新前插入环检测 | P6175 |
| 枚举优化 | Floyd 预处理 + 枚举点对 | P6464 |
| 路径打印 | 维护pre 数组，递归回溯 |
P1347 |
一句话总结：Floyd 的本质是 DP，\(k\) 是"允许经过的中转点集合"。所有变式都是围绕 \(k\) 循环做文章——拆开它、插入操作、改变运算、记录路径。理解 \(k\) 的含义，Floyd 就通了。