网络流

1956 年，美国空军系统分析师 T.E. Harris 写了一份机密备忘录，估算若苏联遭受核打击后，铁路网络能承载多少物资流量。这个问题后来成为一道经典算法题目的直接来源。同年，L.R. Ford Jr. 和 D.R. Fulkerson 在 Canadian Journal of Mathematics 上发表了"最大流-最小割定理"，奠定了网络流理论的基础。

从军事物资调配，到航空公司航班安排，从通信网络带宽分配，到二部图匹配——网络流是组合优化中最有力的工具之一。

核心概念#

流网络（Flow Network）是一个有向图 $G = (V, E)$，每条边 $(u, v)$ 有容量（capacity） $c(u, v) \geq 0$。有两个特殊节点：源点（source） $s$ 和汇点（sink） $t$。

流（flow） $f$ 是对每条边的实数赋值，满足：

1. 容量约束：$0 \leq f(u, v) \leq c(u, v)$（不超过容量）
2. 流量守恒：对所有非 $s, t$ 节点，流入等于流出

流的值 $|f|$ = 从 $s$ 流出的净流量。最大流问题：找流 $f$，使 $|f|$ 最大。

最大流-最小割定理#

割（cut）是节点集合的划分 $(S, T)$，其中 $s \in S, t \in T$。割的容量 = 从 $S$ 到 $T$ 的边的容量之和。

最大流-最小割定理（Max-Flow Min-Cut Theorem，Ford & Fulkerson 1956）：

$$\text{最大流} = \text{最小割容量}$$

这是网络流理论的基石。它意味着：网络能传输的最大流量，恰好等于"切断所有从 $s$ 到 $t$ 的路径"所需要切断的最小容量。直觉上，最小割就是网络的"瓶颈"——流必须经过这里，而容量就是上限。

Ford-Fulkerson 方法#

基本思想：重复找增广路，直到无法找到。

增广路（Augmenting Path）：在残差网络（Residual Graph） $G_f$ 中，从 $s$ 到 $t$ 的路径。残差网络中，每条正向边有剩余容量 $c(u,v) - f(u,v)$，同时每条已有流量的边有反向边，容量为 $f(u,v)$（允许"撤销"部分流量）。

Ford-Fulkerson 框架：
初始化所有流为 0
while 在残差网络 G_f 中存在从 s 到 t 的路径 p:
    瓶颈量 = p 上的最小残差容量
    沿 p 增加流量（正向边增，反向边减）
```

时间复杂度：若用 DFS 找增广路，每次流量至少增加 1（整数情况），最坏 $O(|E| \cdot |f^*|)$（$f^*$ 为最大流值）。若容量为无理数，Ford-Fulkerson 可能不终止——后文有具体机制。

Edmonds-Karp 算法#

Jack Edmonds 和 Richard Karp 在 1972 年提出：用 BFS（广度优先搜索）找增广路，也就是每次都取当前残差网络里最短的增广路。这一简单改变带来多项式时间保证：

$$O(VE^2)$$

这个界从哪来，值得拆开看，因为它是"为什么最短路优先有用"的完整答案。

记 $\delta(v)$ 为残差网络中 $s$ 到 $v$ 的 BFS 层数。第一条引理：每次增广后，任何节点的 $\delta$ 都不会变小——增广只会删掉饱和的边、加上反向边，而反向边总是从深层指回浅层，不可能开出更短的捷径。

第二条引理更关键。称边 $(u,v)$ 在某次增广中是关键边，如果它正是那条路上剩余容量最小的边——它被打满、从残差网络里消失。此刻必有 $\delta(v) = \delta(u) + 1$。这条边要想重新出现，只能靠后来某次增广走了反向边 $(v,u)$，那时 $\delta'(u) = \delta'(v) + 1$。结合第一条引理 $\delta'(v) \ge \delta(v)$，得到

$$\delta'(u) \ge \delta(v) + 1 = \delta(u) + 2$$

也就是说，一条边每次重新成为关键边，它起点的层数就至少涨 2。层数上限是 $V$，所以每条边至多当关键边 $O(V)$ 次。每次增广至少产生一条关键边，故增广总次数 $O(VE)$；每次 BFS 花 $O(E)$，合起来 $O(VE^2)$。

这个证明里没有一处用到容量的大小——这正是 Edmonds-Karp 的价值所在：它把复杂度从"依赖数值"变成了"只依赖图的形状"。

手算一遍：Edmonds-Karp 走完一张 5 节点网络#

光看复杂度证明不解渴。下面这张网络只有 5 个节点、7 条边，可以把每一轮都算完。

源边（离开 s）：   s ──8──→ a       s ──6──→ b
中间边：           a ──3──→ b       a ──5──→ c       b ──4──→ c
汇边（进入 t）：   b ──5──→ t       c ──7──→ t
```

七条边，四层结构：$s$ 只能经 $a$、$b$ 出发，$t$ 只能从 $b$、$c$ 进入，中间三条边负责在 $a\to b\to c$ 之间重新分配流量。

先用最小割猜答案。枚举所有把 $s$ 和 $t$ 分开的划分：

最小割是 12。所以最大流也该是 12——现在让算法自己跑出这个数。

逐轮增广（每轮 BFS 取最短增广路；表中"残量"列出 7 条正向边的剩余容量，顺序为 $s\!\to\!a$ / $s\!\to\!b$ / $a\!\to\!b$ / $a\!\to\!c$ / $b\!\to\!c$ / $b\!\to\!t$ / $c\!\to\!t$）：

这张表最该注意的是"路长"那一列：2、3、3、4，单调不减。这正是上一节第一条引理的实物证据——Edmonds-Karp 的收敛过程就是增广路一层层变长的过程，长到超过 $V-1$ 就必然结束。

最终流量分配：$s\to a$ = 6，$s\to b$ = 6，$a\to b$ = 1，$a\to c$ = 5，$b\to c$ = 2，$b\to t$ = 5，$c\to t$ = 7。逐点验守恒：$a$ 进 6、出 $5+1=6$；$b$ 进 $6+1=7$、出 $5+2=7$；$c$ 进 $5+2=7$、出 7。流入 $t$ 的总量 $5+7=12$，与最小割吻合。

还有一个漂亮的收尾。第 5 轮 BFS 停下时，从 $s$ 在残差网络里能走到的节点集恰好是 $\{s,a,b,c\}$——这就是最小割的 $S$ 侧，跨割的边 $b\to t$（5）和 $c\to t$（7）刚好都被打满。最大流-最小割定理不是一个需要另外证明的定理，它就是算法终止那一刻的现场照片：算法停下来，是因为再没有路可走；而"再没有路可走"的另一个名字，就是"存在一个饱和的割"。

反向边不是技巧，是必需品#

初学者最容易砍掉的就是残差网络里的反向边——看起来像多余的簿记。下面这个 4 节点网络证明砍不掉。

边与容量：$s\to a$ = 3，$s\to b$ = 3，$a\to b$ = 3，$a\to t$ = 3，$b\to t$ = 3。

最大流是 6（$s\to a\to t$ 走 3，$s\to b\to t$ 走 3，两条源边和两条汇边全部打满；最小割 $\{s\}$ 侧容量 $3+3=6$，$\{s,a,b\}$ 侧也是 6）。

现在假设算法运气不好，第一条找到的增广路是 $s\to a\to b\to t$，瓶颈 3：

没有反向边的版本到此为止：$s\to a$ 满了，$s\to b$ 还剩 3 但 $b\to t$ 已经满了，$b$ 是死路。算法宣布最大流 = 3，答案只有真值的一半。

有反向边的版本还能走一步。$a\to b$ 上流着 3，于是残差网络里存在反向边 $b\to a$，容量 3。BFS 找到 $s\to b\to a\to t$，瓶颈 $\min(3,3,3)=3$：

注意中间那一列：走反向边 $b\to a$ 的效果，是把 $a\to b$ 上原本那 3 个单位的流量撤回。撤回后 $a$ 手上多出 3 个单位无处可去，正好推给 $a\to t$；而 $b$ 失去的那 3 个单位，由新来的 $s\to b$ 补上。贪心走错的一步被完整地"改判"了，而算法自己并不知道它在纠错——它只是在残差网络里找了一条路。

该记住的是：反向边把"局部贪心 + 允许回退"变成了"全局最优"。这是网络流最深的一层设计——不要求每一步都对，只要求每一步都可逆。Ford-Fulkerson 的正确性证明（无增广路 $\Rightarrow$ 最优）整个建立在这一点上。

失败现场：无理容量下永不终止#

Ford-Fulkerson 的复杂度界 $O(E \cdot |f^*|)$ 里含着一个前提：容量是整数，所以每轮流量至少涨 1。容量取无理数时，这个前提消失，算法可以永远跑不完。

机制是这样的。取 $r = \frac{\sqrt5 - 1}{2} \approx 0.618$，它满足 $r^2 = 1 - r$，两边乘 $r^n$ 得

$$r^{n+2} = r^n - r^{n+1}$$

这个恒等式可以被用来搭一张网络：让第 $n$ 轮增广的瓶颈恰好是 $r^n$，而增广完的残量刚好又摆成同一个形状，于是第 $n+1$ 轮的瓶颈是 $r^{n+1}$。轮次无限，每轮都真的推进了流量，但推进量按几何级数衰减。总流量收敛到

$$\sum_n r^n < \infty$$

一个有限的数——而且这个数严格小于最大流。算法既不终止，也不收敛到正确答案。

Ford 和 Fulkerson 自己给的反例有 10 个节点、48 条边。Uri Zwick 在 1995 年把它压到了极致：两个 6 节点 9 边的网络，以及一个 6 节点 8 边的网络，并证明 8 条边是不可能再少的下限（Theoretical Computer Science 148(1)）。

这件事的工程含义比它的理论含义更实在：浮点容量不是"无理容量"的安全近似。用 double 存容量时，瓶颈会小到被舍入吞掉，算法不会死循环，但会在某个说不清的地方提前停下，给出一个说不清的答案。工业实现（包括下文的图割库）一律用整数容量，需要小数就先统一乘一个比例因子取整——这不是洁癖，是上面那个几何级数留下的教训。

Dinic 算法#

Yefim Dinitz（苏联计算机科学家，名字有时拼写为 Dinic）在 1970 年提出阻塞流（Blocking Flow）的概念，达到 $O(V^2 E)$ 的时间复杂度。

思路上它是 Edmonds-Karp 的加强版：不是每轮找一条最短增广路，而是先按 BFS 层数建出分层图，然后在这一层结构上一次榨干所有等长的增广路（这就是"阻塞流"），才重新分层。相同层数的增广路被批量处理，分层次数因此只有 $O(V)$ 轮。

对于单位容量图（如二部图匹配），Dinic 算法更快：$O(E \sqrt{V})$。Dinic 是竞技编程中求最大流的首选算法。

应用：二部图最大匹配#

网络流最优雅的应用之一是二部图最大匹配（Bipartite Maximum Matching）。

问题：有 $m$ 名工人和 $n$ 项工作，每名工人能胜任某些工作，找最多的"工人-工作"配对（每人每工作至多一对）。

建图：源点 $s$ 连向所有工人，容量 1；每名工人连向其能胜任的工作，容量 1；所有工作连向汇点 $t$，容量 1；求最大流。

最大流值 = 最大匹配数。容量 1 承担了全部约束：源边容量 1 保证每名工人至多接一份活，汇边容量 1 保证每份活至多派一人，流量守恒保证不会有"半个匹配"。这将匹配问题规约为流问题，结构之简洁令人叫绝。

König 定理（1931，Dénes König）：在二部图中，最大匹配数 = 最小顶点覆盖数。这是最大流-最小割定理的组合版本。

最小费用最大流#

若每条边不仅有容量 $c(u,v)$，还有单位流量的费用（cost） $w(u,v)$，则最小费用最大流（Min-Cost Max-Flow）在所有最大流中找费用最小的。

算法：用 Bellman-Ford 或 SPFA（Shortest Path Faster Algorithm）在残差网络中找最短（最小费用）增广路，重复增广。注意这里为什么不能直接上 Dijkstra——残差网络里的反向边费用是 $-w(u,v)$，负权天然存在。想用 Dijkstra 就必须先做 Johnson 式的势函数重标（potential reweighting），把边权改造成非负。

应用：运输规划、任务分配（最小总成本匹配）、流水线调度。

更强大的推进-重标（Push-Relabel）算法#

Andrew Goldberg 和 Robert Tarjan 在 1986 年提出 Push-Relabel 算法，理论复杂度 $O(V^2 E)$ 或 $O(V^3)$（各种变种），在稠密图上实践表现极佳。

它打破了"增广路"的框架，用"高度函数"和局部推流操作代替全局路径搜索，是最大流算法设计的里程碑。

复杂度这七十年：从"依赖流量大小"到几乎线性#

最大流是算法复杂度史上被反复攻克的靶子，几个关键刻度值得记住：

最后一行是 2022 年 FOCS 最佳论文：整数容量与费用下的最大流与最小费用流可以在几乎线性时间内精确求解。它的技术路线与前面所有算法都不同——不再是增广路或推流，而是把流问题当作一个连续优化问题，用内点法迭代，每一步靠一个动态图数据结构维护"近似最小比例环"。

这条线索该记住的是方法论的转向：2010 年之后最大流的所有重大进展都来自连续优化与谱图论，而不是组合方法。同一个问题，换一种数学语言重新表述，天花板就换了位置。代价是这些算法目前只有理论意义——$m^{o(1)}$ 里藏着的常数使它们在任何现实规模上都跑不过 1986 年的 Push-Relabel。

计算机视觉中的图割#

2000 年代，Yuri Boykov、Vladimir Kolmogorov 等人把最小割搬进了计算机视觉。这不是"网络流也能用于图像"这么模糊的一句话，而是一次精确的等价转换，值得看清具体怎么建图。

建图规则（以前景/背景二分割为例）：

• 每个像素是一个节点。图里另加两个终端：源点 $s$ 代表"前景"标签，汇点 $t$ 代表"背景"标签。
• 终端边：像素 $p$ 到 $s$ 的容量取 $-\ln \Pr(Ip \mid \text{背景})$，到 $t$ 的容量取 $-\ln \Pr(Ip \mid \text{前景})$——由用户涂抹的样本区域拟合出的颜色模型给出。切断哪条终端边，就等于把该像素判给另一侧。
• 邻接边：相邻像素 $p,q$ 之间的容量是平滑项，典型形式 $\exp(-\|I_p - I_q\|^2 / 2\sigma^2)$：颜色相近的邻居之间边很重，割开代价高；跨越颜色跳变（也就是真实边界）的地方边很轻，割开便宜。

于是任意一个 $s$-$t$ 割就是一次前景/背景标注，割的容量就是这次标注的能量。求最小割 = 求能量最小的标注，也就是这个二值马尔可夫随机场的全局最优 MAP 解。注意"全局最优"这个词的分量：图像分割的能量函数在一般情况下是 NP-hard 的，图割能拿到全局最优，靠的是一个结构条件。

Kolmogorov 与 Zabih 在 2004 年把这个条件说清楚了（IEEE TPAMI 26(2)）：二值能量能用图割精确最小化，当且仅当其两两项满足

$$E(0,0) + E(1,1) \le E(0,1) + E(1,0)$$

这就是子模性（submodularity）——直白说是"邻居标签一致要比不一致便宜"。平滑项天然满足它，所以分割能过关；一旦模型里出现鼓励标签不一致的项，图割立刻失效，只能退回近似方法。

工程上还有一处细节值得注意：这类图的形状很特殊——几十万到上千万个节点，但每个节点只有 4 或 8 个邻居，极度稀疏，且大量流量在局部来回。Boykov 与 Kolmogorov 在 2004 年的实验对比（IEEE TPAMI 26(9)）表明，在这种形状上，通用的 Push-Relabel 实现反而输给他们专门设计的增广路算法——后者复用两棵搜索树，避免每轮从头 BFS。这是"渐进复杂度不决定胜负"的又一个例子：赢的是那个针对图的形状做了假设的实现。

跨域连接#

• 线性规划：最大流是一个线性规划，最小割是它的对偶，强对偶定理就是最大流最小割定理。额外的关键事实是约束矩阵全单模——它保证对偶最优解可以取到整数，割才有"切断哪几条边"的组合意义。一般整数规划做不到这一点，这正是流问题好解而多数组合优化不好解的分界。
• 图论：König 顶点覆盖定理、Menger 连通度定理、Hall 婚配定理是同一个定理在不同语言下的投影，证明都可以规约成"建一张流网络，读它的最小割"。记住这条比分别背四个定理有用：碰到"最少删多少点或边才能断开"这类命题，先去找它的流模型。
• 生物能量学与代谢：代谢网络的稳态假设就是流量守恒，通量平衡分析把"细胞最快能长多快"写成带上下界的线性规划。对偶变量在这里有生物含义：影子价格非零的反应是瓶颈，敲除它会直接压低生长速率；影子价格为零的反应敲掉几乎无感。这条预测可以被基因敲除实验证伪。
• 计算机视觉：图像分割的能量最小化一般是 NP 难的，图割却能拿全局最优，条件是两两项满足子模性——直白说是"邻居标签一致比不一致便宜"。模型里一旦出现鼓励标签不一致的项，最小割立刻失效，只能退回近似。能不能精确求解由结构条件而非问题规模决定，这是最干净的一个例子。
• 搜寻与匹配理论：二部图最大匹配给出的是"技能与岗位在图上最多配成几对"的组合上界。劳动经济学关心的恰是现实为何达不到这个上界——搜寻摩擦、信息不完全、双方都在等更好的对象，这些都不在容量为一的边里。把失业解释成"图上匹配不足"是误读：图只画了可行性，没画时间与信息成本。

参考文献#

• Ford, L.R. & Fulkerson, D.R. "Maximal Flow Through a Network." Canadian Journal of Mathematics 8, 1956.
• Edmonds, J. & Karp, R.M. "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems." Journal of the ACM 19(2), 1972.
• Zwick, U. "The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate." Theoretical Computer Science 148(1), 165–170, 1995.
• Goldberg, A.V. & Tarjan, R.E. "A New Approach to the Maximum-Flow Problem." Journal of the ACM 35(4), 1988.
• Orlin, J.B. "Max flows in O(nm) time, or better." STOC 2013, 765–774.
• Chen, L., Kyng, R., Liu, Y.P., Peng, R., Probst Gutenberg, M. & Sachdeva, S. "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time." FOCS 2022（最佳论文）. arXiv:2203.00671.
• Boykov, Y. & Kolmogorov, V. "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision." IEEE TPAMI 26(9), 1124–1137, 2004.
• Kolmogorov, V. & Zabih, R. "What Energy Functions Can Be Minimized via Graph Cuts?" IEEE TPAMI 26(2), 147–159, 2004.
• Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022.（第 24、26 章）

延伸阅读#

• Ahuja, R.K., Magnanti, T.L. & Orlin, J.B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.（网络流的标准参考书）
• Schrijver, A. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003.（第 10–15 卷讲流与割的多面体视角）
• Williamson, D.P. Network Flow Algorithms. Cambridge University Press, 2019.（含 2010 年后连续优化路线的入门介绍）