当前位置：首页 > news >正文

图论-Floyd算法学习笔记

news 2026/8/1 20:53:01

Floyd 算法学习笔记

核心思想

Floyd 算法基于 DP，只要记住 k 点在最外层 就可以。

就是一个搭桥思想：看 \(u \to v\) 是否可以被一个点 \(k\)，使得 \(u \to k + k \to v\) "抄小路"。

\[f[u][v] = \min(f[u][v], f[u][k] + f[k][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] = \min(f[k-1][u][v], f[k-1][u][k] + f[k-1][k][v]) \]

其中 \(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 换成 | 和 & 就行：

\[f[u][v] = f[u][v] \mid (f[u][k] \& f[k][v]) \]

\(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