Ford–Fulkerson 方法 | Codeboy's Blog

形式陈述

给定容量网络，Ford–Fulkerson 从零流开始。对当前可行流 $f$ 构造带原弧身份的残量有向多重图，反复寻找一条从 $s$ 到 $t$ 的简单残量路 $P$ ，令瓶颈

\Delta=\min_{r\in P}c_f(r),

并沿 $P$ 增广 $\Delta$ ：经过原弧的正向记录就增加该弧流量，经过反向记录就减少相应原弧流量。瓶颈保证每条更新后仍在 $[0,c(a)]$ 内；路径的每个内部顶点获得的一入一出改变量相消，所以守恒保持，流值增加恰好 $\Delta$ 。

若残量图中不再有 $s\leadsto t$ 路，令 $S$ 为从 $s$ 残量可达的顶点。所有从 $S$ 指向补集的原弧均饱和，所有从补集指向 $S$ 的原弧流量均为零，于是割容量等于当前流值；由最大流最小割定理，当前流最大。因此 Ford–Fulkerson 是由“如何选择增广路”参数化的方法框架，而非一个已固定运行时间的单一算法。

若容量为非负整数，每次 $\Delta\ge1$ ，从零流出发至多增广 $|f^*|$ 次。用邻接表在 $O(|V|+|A|)$ 时间搜索并更新一条路，去掉无关孤立点后常写成 $O(|A|\,|f^*|)$ ；这是依赖数值大小的伪多项式界。精确有理容量乘以共同分母后也会终止，但迭代界随缩放后的最大流增长。对任意实容量与任意选路规则，过程可能无限增广，甚至不收敛到最大值。

直觉

一次增广把整条残量路看成可同时调整的方向链，瓶颈是这次最多能推多少。正向记录使用尚空容量，反向记录撤销旧流；早期路径因此不是不可逆承诺。

停止证书来自全局不可达性，而非“刚才选的路已经满”。只要还有残量源汇路，就存在严格增加流值的可行改动；当所有这类路消失，残量可达集恰好暴露一个与当前流同值的割。

残量路经反向弧撤销旧流并把流值从一增至二 — Ford–Fulkerson 的正反残量更新

例子与边界

弧

s\to a,\ s\to b,\ a\to b,\ a\to t,\ b\to t

容量均为 $1$ 。若先沿 $s\to a\to b\to t$ 增广，得到 $f(s,a)=f(a,b)=f(b,t)=1$ 。此时第二条残量路是

s\to b\to a\to t,

其中 $b\to a$ 是原弧 $a\to b$ 的反向记录。增广后 $f(a,b)$ 降为 $0$ ，同时 $f(s,b)=f(a,t)=1$ ，最终等价于两条单位路径 $s\to a\to t$ 与 $s\to b\to t$ 。若搜索只看原弧的正向余量，就会错误停在流值 $1$ 。

反平行原弧与残量反向记录方向可能相同，更新时必须通过配对索引找到各自原弧；只用端点定位会在撤销时改错记录。平行弧也应分别保存容量与残量，或在不需要逐弧输出时预先合并容量。

大整数容量说明终止不等于高效：容量用二进制写入时， $|f^*|$ 可相对输入位数呈指数级。Edmonds–Karp 固定选残量边数最少的路，给出 $O(|V||A|^2)$ 的组合界；Dinic 在每个最短距离层次中一次求阻塞流。二者的多项式性来自选路结构，不来自把容量声明为整数。

推论与应用

增广思想把二分图匹配中的交替路、单源单汇流与某些环流可行性算法放进同一残量语言。最小费用流还要比较增广费用并防止负费用圈，带下界环流要先恢复可行初始流；它们不能只沿任意残量路重复本页步骤。

Ford–Fulkerson 始终维护满足守恒的可行流，并按完整源汇路增加流值。Push–Relabel允许中间状态违反守恒而形成预流，只沿局部 admissible edge 推送超额；两者的状态空间、终止条件与复杂度势函数不同。

任一可行流可由流分解定理写成路径流与环流之和，这解释增广的路线语义，却不保证任意选路具有多项式迭代数。

参考资料

L. R. Ford Jr. and D. R. Fulkerson, “Maximal Flow Through a Network,” Canadian Journal of Mathematics 8, 1956, pp. 399–404。
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§24.2。
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 7。

形式陈述 ​

反向链接

形式陈述