Edmonds-Karp · BFS 最短增广路 · O(VE²)

Edmonds-Karp:BFS 找最短增广路

最大流与残量网络的 Ford-Fulkerson 框架只说了一句「在残量网络里找一条增广路」，却没规定怎么找。这个未定的自由度，正是朴素实现可能很慢、甚至在某些容量下不终止的根源。Edmonds-Karp 对 Ford-Fulkerson 只做了一处改动：把「任取一条增广路」换成「用 BFS 找边数最少（最短）的增广路」。就这一个限定，把整套算法的复杂度钉死在 O(VE²)，且与容量数值完全无关。

1 · 为什么「任取一条增广路」会慢

增广路怎么选不影响正确性（最终都能到达最大流），却剧烈影响增广次数。DFS 任取一条路，在某些网络上会被一条窄边反复牵着走：每次都贪心地把流量挤过那条容量极小的边，下一步再借反向边把它退回、改道，如此往返。每一轮往返才推进一个单位，于是增广次数与容量的数值挂钩——容量越大，来回腾挪越多。

经典坏例子。 取一张「中间瓶颈网」： $s\to a$ 、 $s\to b$ 、 $a\to t$ 、 $b\to t$ 容量都很大（这里取 6），正中间却横着一条容量仅 1 的边 $a\to b$ 。若每次增广都「不巧」选了穿过中间边的路 $s\to a\to b\to t$ ，只能推 1 个单位（被中间边卡死）；接着必须走 $s\to b\to a\to t$ （其中 $b\to a$ 是反向边）把这 1 个单位退回、改道，又只推 1。两侧容量为 k 时，这样一来一回要 2k 次增广才能填满。

更极端：无理容量下 FF 可能永不终止。 Ford 与 Fulkerson 自己给过一个含无理数容量（与黄金比例相关）的网络：若每次都按最坏顺序选增广路，瓶颈值构成一个几何衰减的无穷序列，流值收敛到一个低于真实最大流的极限，增广永远停不下来。问题的根子全在「任取」——只要换成 BFS 选最短路，这些病态情形一概消失。

直觉是：窄边 $a\to b$ 本不该参与主干输送。从 s 到 t 其实有两条各只有两段的捷径（ $s\to a\to t$ 与 $s\to b\to t$ ），完全绕得开它。问题只是 DFS「看不见」哪条更短。把找路换成 BFS，天然优先走段数少的，中间那条窄边就再也不会被选中。

2 · 最短增广路：O(VE²) 的来历

Edmonds-Karp = Ford-Fulkerson +「每次都在残量网络上用 BFS 找边数最少的增广路」。BFS 把每个点到源 s 的层距（最少边数）算出来，沿层距严格递增的路径回溯，就是一条最短增广路。下面这套引理把增广次数从「与容量有关」彻底解放成「只与图规模 V, E 有关」。

引理一：层距单调不减。 每次沿最短增广路增广后，残量网络中每个点到 s 的 BFS 层距都不会变小。

记第 k 次增广前、点 v 到源的层距为 d_k(v)。要证 d_{k+1}(v) ≥ d_k(v)。一次增广只会：把增广路上某些正向边推满（从残量网络删去），并可能新增一些反向边。删边不会让任何点更靠近 s。唯一可能「抄近路」的是新出现的反向边 $v\to u$ ，但它出现的前提是这次增广用到了正向边 $u\to v$ ，而那条边在最短增广路上，必有 d_k(v) = d_k(u) + 1，即 u 比 v 离源更近一层。于是经由新反向边 $v\to u$ 反而是「往回走」，绕不出更短的路。归纳即得层距单调不减。∎

引理二：每条边当「关键边」最多 O(V) 次。 一次增广的瓶颈边称为关键边 (critical edge)；同一条边被选为关键边的次数是 O(V)。

设某条正向边 $u\to v$ 在第 k 次增广时是关键边（它被推满，从残量网络消失）。因为这条路最短，有 d_k(v) = d_k(u) + 1。这条边要想再次成为关键边，必须先重新出现在残量网络里；而它重现的唯一途径，是后续某次增广走了它的反向边 $v\to u$ （把流量退回去）。设那次发生在第 k' > k 次，则那条最短路上有 d_{k'}(u) = d_{k'}(v) + 1。结合引理一 (d_{k'}(v) ≥ d_k(v)) 推得 d_{k'}(u) = d_{k'}(v) + 1 ≥ d_k(v) + 1 = d_k(u) + 2。也就是说 u 的层距每经历一轮「关键 → 复活 → 再关键」就至少 +2。层距上界是 $V-1$ ，故 $u\to v$ 最多当 $O(V)$ 次关键边。∎

合成：总增广次数 O(VE) → 总复杂度 O(VE²)。

每次增广至少有一条关键边。残量网络含 $O(E)$ 条边（每条原边一正一反），每条边最多当 $O(V)$ 次关键边（引理二），所以增广总次数是 $O(VE)$ 。每次增广要跑一遍 BFS，代价 $O(E)$ 。两者相乘：O(VE²)。关键在于这个界只含 V、E，与边上容量的大小、是否为整数、是否为无理数统统无关——这就是为什么 EK一定终止，而朴素 FF 在无理容量下可能不终止。∎

一句话记忆。「最短增广路」让每条边的层距只能越走越远，层距有限 (≤ V−1)，于是每条边只能被「用尽——复活」有限次，增广总次数被图规模锁死，与容量脱钩。代价仅仅是把找路的 DFS 换成 BFS。

3 · 逐步对比：Edmonds-Karp vs 朴素 Ford-Fulkerson

同一张「中间瓶颈网」（中间边 $a\to b$ 容量仅 1，两侧容量 6，最大流 = 12）。用下面的下拉切换找增广路的策略，切换即重置。对比两种策略:BFS (Edmonds-Karp) 只需 2 次增广——直接走 $s\to a\to t$ 、 $s\to b\to t$ 两条捷径，根本不碰中间那条窄边；DFS（朴素 Ford-Fulkerson） 却要 4 次——先两次傻乎乎地穿过中间边，再靠一条反向边把流量退回改道。EK 模式下，增广帧还会按 BFS 层距给节点分层着色并标 Lk。

这一步说明了什么。 两种策略最大流都是 12（正确性与选路无关），但 EK 的 BFS 让每次增广都走最短捷径，2 次即满；DFS 任取则被中间窄边反复牵制，4 次才到顶（本例容量小，差距是 2 倍；把两侧容量调大，DFS 的次数会随容量线性膨胀，而 EK 始终是 2）。

接下来： EK 已把找路换成 BFS，但每次增广仍只推一条路、且每次都从头跑一遍 BFS。Dinic 把 BFS 得到的分层图留下来，一个相位内用 DFS 一次推出阻塞流 (blocking flow)——在同一层次图上把所有最短增广路一次性榨干，复杂度进一步降到 O(V²E)。