形式陈述

给定容量网络与当前可行流 $f$$f$，残量网络含正向残量 $c_f(u,v)=c(u,v)-f(u,v)$$c_f(u,v)=c(u,v)-f(u,v)$ 以及允许撤销流的反向残量。Ford–Fulkerson 反复找一条 $s$$s$ 到 $t$$t$ 的增广路，按路径最小残量 $\Delta$$\mathrm{\Delta }$ 增广，直到不存在增广路。由最大流—最小割定理，此时流最大。容量为整数时每次至少增广 1，算法终止且运行时间 $O(|E|\,|f^*|)$$O(|E||f^{\ast }|)$；任意实数容量和任意选路规则可能不终止。

直觉

已有决策并非不可撤销：残量反向边允许把先前送错方向的流退回，再改走更好的路线。没有任何剩余源汇通路时，已达可证明的割上限。

例子与边界

若先沿共享瓶颈选了不佳路径，后续增广可通过反向边改道。只在原图剩余容量边上找路会错过这种调整。流值必须满足容量与除源汇外流守恒。整数容量保证整数流；无理容量可构造无限逼近而不终止的选路序列。Edmonds–Karp 用 BFS 选最短增广路，给出与流值无关的多项式界。

推论与应用

该方法是最大流算法的基本框架，衍生匹配、割、可行循环和许多组合优化算法，并揭示残量图与对偶证书的关系。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。