第二季 · 第 37 章

水管、铁路与最大流

《算法的故事》第二季 · 第二篇：寻找世界的最优解——福特、富尔克森与网络中隐藏的瓶颈

1955年，美国加利福尼亚州，圣莫尼卡。在兰德公司，一群数学家和研究人员正在研究一个看起来很普通的铁路运输问题。假设一张铁路网连接着许多城市。每条铁路都有自己的运输能力。有些线路每天能够通过数十列火车，有些线路只能通过几列。货物可以沿不同路线前进，也可以在中途转运。现在，人们希望知道：从一座城市出发，经过整个铁路网络，每天最多能向另一座城市运送多少货物？这个问题似乎并不困难。只要找到运输能力最大的线路，让货物尽可能多地通过，不就可以了吗？但事情并没有这么简单。一条铁路的运输能力很大，不代表它通往目的地的其他线路也足够宽敞。某些车站可能积压大量货物，而另一些车站却拥有空闲线路。甚至存在一种奇怪的情况：整个网络里每条路线看起来都已经无法增加运输量，但通过重新安排已经分配的货物，仍然可以让更多货物抵达终点。为了找到真正的最大运输量，数学家必须解答两个问题。第一，怎样找到更好的运输方案？第二，怎样证明这已经是整个网络能够达到的极限？这项研究最终与两位数学家的名字紧密联系在一起。莱斯特·伦道夫·福特二世（Lester R. Ford Jr.）。德尔伯特·雷·富尔克森（Delbert Ray Fulkerson）。他们发展的最大流理论，让一道交通运输题，变成了现代图算法中最重要的问题之一。而其中最令人惊叹的发现是：一个网络能够输送多少东西，最终竟然由一道最窄的“割”决定。

第一幕：冷战时期，一张铁路地图上的数学问题

20世纪50年代铁路货运的历史环境。铁路系统承担大规模资源运输，线路容量、换装能力与瓶颈位置都具有重要意义。图片为时代背景，并非兰德公司的原始研究地图。第二次世界大战结束后，世界进入冷战时期。铁路仍然是欧亚大陆重要的运输基础设施。对于工业生产、跨地区物资分配和军事后勤来说，铁路网络具有不可替代的作用。一条重要干线中断，可能影响许多地区。但如果存在备用线路，货物就可能绕行。因此，只关注单条铁路的运输能力，并不足以判断整个交通系统的能力。研究人员需要一种能够把全部线路放在一起分析的方法。

哈里斯与罗斯：问题最初来自哪里？

兰德公司的研究人员 T. E. Harris，与退役美国陆军将领 F. S. Ross，研究过铁路网络的整体运输能力。他们将复杂铁路系统抽象为一张网络图。城市、铁路运营分区或交通枢纽可以表示为节点。连接这些节点的铁路线路则表示为边。每条边附带一个数字，代表它在给定时间内能够承担的运输容量。这样，原本包含大量地理细节的铁路系统，就能够被转化为一个数学对象。1955年10月24日，他们完成了一份研究报告：Fundamentals of a Method for Evaluating Rail Net Capacities《评估铁路网络容量的一种方法的基础》。这份报告原本具有保密性质。直到1999年5月21日，美国国防部才将其降为非密级。后来，数学家 Alexander Schrijver 专门研究了这段历史，重新梳理了这份报告及其对最大流研究的影响。^{[EMS Press][Paperzz]}

真实的铁路网有多复杂？

哈里斯与罗斯的报告研究了苏联西部及东欧地区的铁路网络。经过将铁路运营分区聚合为节点，所使用的模型包含：

图37-1：1955年铁路网络研究的规模

44

网络节点

105

无向连接

163,000

吨 · 报告中的流量值

Schrijver 对原始报告的考证：铁路模型为44个节点、105条无向连接；报告获得的流量和对应割容量均为163,000吨。不能将该数值直接解释为对今天铁路系统的运输能力估计。^{[Paperzz][EMS Press]}

最初的研究目的，还包含一个比“怎样运输更多货物”更复杂的历史背景。研究者希望识别铁路网络中影响整体运输能力的关键位置，为军事战略分析提供依据。因此，这段历史并不是纯粹的商业物流故事。但这些研究所揭示的数学结构，也能用于和平时期的铁路调度、物流规划和通信网络容量分析。在这里，我们将只研究通用的网络容量问题，不涉及针对实际交通系统实施破坏的方案。

一份论文从这个问题开始

1956年，福特与富尔克森在《加拿大数学杂志》发表了论文：Maximal Flow Through a Network《通过网络的最大流》。论文开头直接引用了 Harris 对铁路网络问题的描述。研究者希望给定网络中每条线路的容量，然后求出从指定起点到指定终点的最大稳定流量。这篇论文只有六页，但其中心结论后来成为组合优化的经典定理之一。^{[Cambridge Core][cs.yale.edu]}

1956年《Maximal Flow Through a Network》论文首页。其原始论文提交日期为1955年9月20日，正式发表于1956年第8卷，第399—404页。^{[Cambridge Core]}值得注意的是，原始资料存在一些时间上的细节。福特与富尔克森有关最大流定理的兰德技术报告，标注日期为1954年11月19日；而他们在1962年的著作中，又回忆铁路问题是1955年春天由 Harris 提出的。这些日期并不能毫无矛盾地拼接成一条简单时间线。数学史研究者明确指出了这一不一致。因此，我们可以确认1954—1957年间相关研究与发表的脉络，却不应编造某次精确到月份的会谈，解释这些资料尚未解决的历史疑点。^{[Paperzz][JSTOR]}真正值得讨论的是，这样一个铁路问题，为什么能够引出深刻的数学定理？首先，我们需要学会把铁路变成一张数学上的网络。

第二幕：福特与富尔克森，把运输问题变成一张图

德尔伯特·雷·富尔克森（1924—1976），美国数学家。他在兰德公司从事线性规划、组合优化与网络流研究，并与福特长期合作。^[INFORMS]富尔克森出生于美国伊利诺伊州南部。第二次世界大战期间，他曾在美国陆军航空队服役，并接受过气象方面的学习。战后，他回到大学完成学业。1951年，他在威斯康星大学获得代数学博士学位，随后进入兰德公司的数学研究部门。在那里，他接触到了丹齐格的线性规划研究，以及其他运筹学家的优化工作。他的同事中，有 George Dantzig、Merrill Flood、Lloyd Shapley 等数学和运筹学研究者。另一位重要的合作者，是莱斯特·伦道夫·福特二世。两人在网络流领域展开了长期合作，并于1962年出版《Flows in Networks》，将网络流理论整理成更为系统的数学体系。^{[INFORMS][JSTOR]}

第一项抽象：城市只是节点

想象一条铁路连接了四座城市。我们不需要首先知道城市拥有多少人口。也不需要关心沿途建筑物的样子。如果研究的只是给定容量条件下的最大运输量，那么可以暂时保留四个节点：

S,\quad A,\quad B,\quad T

其中：

$S$ ：Source，源点，货物出发的地方。
$T$ ：Sink，汇点，货物最终到达的地方。
$A,B$ ：中间节点，代表可以转运的城市或枢纽。

然后，为每条连接设置容量。假设网络拥有五条有向边：

连接	最大容量
S → A	3
S → B	2
A → B	2
A → T	2
B → T	3

这里的容量可以理解成单位时间内允许通过的货物流量。它不一定表示实际列车数量。对于本章的教学模型，我们可以把一个容量单位简单理解成每天能够运输一批标准货物的能力。

图37-2：四个节点、五条线路的运输网络

查看 SVG 配图原件

37-004-41d8b86d88b0.svg · 点击查看大图

现在，我们得到了一个有向图：

G=(V,E)

其中

V

是节点集合，

E

是有向边集合。每条边具有容量：

c(u,v)\ge0

我们要寻找每条边上的实际流量：

f(u,v)

但这些流量不能随意选择。

第二项抽象：每条线路都有容量限制

如果 S 到 A 的容量是3，那么实际流量必须满足：

0\le f(S,A)\le3

如果 A 到 T 的容量是2，那么：

0\le f(A,T)\le2

换句话说：任何一条线路，都不能在给定时间内输送超过自身容量的货物。这称为容量约束。

第三项抽象：中间城市不能凭空制造货物

假设每天有3批货物抵达城市A。那么在没有货物生产、消耗或长期积压的稳态模型中，A每天也必须向外运走3批货物。因此：

\text{流入量}=\text{流出量}

对于一般中间节点

v

，可以写成：

\boxed{\sum_u f(u,v)=\sum_w f(v,w)}

这就是流量守恒（Flow Conservation）。源点和汇点则有所不同。源点负责提供净流量。汇点负责接收净流量。我们希望最大化的，是从源点净流出的流量总量，也等于汇点净流入的流量总量：

\boxed{|f|=\sum_v f(S,v)}

在本例中，源点没有流入边，所以写法可以如此简洁；对于一般网络，还应减去源点的流入量。

这不就是线性规划吗？

完全正确。上一章我们已经学习，怎样通过线性目标与线性约束来表达资源配置问题。最大流问题同样可以写成线性规划。每条边上的流量都是变量。容量限制是线性不等式。中间节点的流量守恒是线性等式。目标是最大化从源点到汇点的流量。福特与富尔克森1956年的论文，开头就明确指出了最大流与单纯形法之间的联系。但是，他们接下来要探索的是：网络具有特殊结构，能不能利用这种结构，设计比通用线性规划求解更直接的算法？这也正是现代算法设计中一个反复出现的主题。通用方法可以解决问题。但如果我们看清了问题隐藏的结构，就可能找到更专门、更有效的计算方法。

第三幕：第一条路线满载了，但整个网络还远没有达到极限

管道网络的分流与汇流结构。与铁路一样，水管具有流动方向、容量限制及节点守恒要求，是理解最大流问题的直观模型。我们先暂时忘记火车。把这五条运输线路想象成五根水管。源点S是一个大型供水池。汇点T是需要接收水的城市。A与B是两个中间水站。每条水管的容量，代表它在单位时间内最多能够输送多少水。现在，我们想让尽可能多的水流到T。你会怎样安排？

第一次尝试：找到一条完整的路

观察网络：

S\rightarrow A\rightarrow B\rightarrow T

这是一条从源点到汇点的完整路径。沿途三条边的容量分别为：

3,\quad2,\quad3

这条路能够一次输送多少流量？答案不是：

3+2+3=8

而是：

\boxed{\min(3,2,3)=2}

因为任何一条路径的运输量，都不能超过沿途容量最小的边。它就像一根由粗细不同的管段连接而成的水管。某个地方即使非常宽敞，只要中间存在一个狭窄管段，整条路径能够稳定通过的流量就受到限制。我们于是沿着这条路送出2单位流量。此时：

f(S,A)=2

f(A,B)=2

f(B,T)=2

其余两条边流量为0。整个网络已经输送：

|f|=2

第二次尝试：再找一条能够送货的路

看看：

S\rightarrow A\rightarrow T

其中，S到A还有1单位剩余容量。A到T的剩余容量为2。因此，这条路径还能增加：

\min(1,2)=1

单位流量。增加之后：

|f|=3

这时，S到A已经满载。

第三次尝试：换一条路线

还可以通过：

S\rightarrow B\rightarrow T

S到B原本容量为2。B到T原本容量为3，但第一次已经使用了2。所以B到T只剩1单位。因此，我们沿着这条路再送出1单位。总流量变成：

\boxed{|f|=4}

现在，网络的状态如下。

图37-3：三次分配后，网络看起来已经无法继续输送

查看 SVG 配图原件

37-007-ce5ae0f2293d.svg · 点击查看大图

边	当前流量	容量上限	可继续正向增加
S → A	3	3	0
S → B	1	2	1
A → B	2	2	0
A → T	1	2	1
B → T	3	3	0

当前总流量

4

现在请仔细观察。S到A已经满载。S到B还有1单位空间。但B到T已经满载。如果我们只考虑沿现有方向继续增加流量，那么从S出发似乎再也找不到一条完整的通路。是不是说明最大流就是4？不对。因为从源点出发的全部容量是：

3+2=5

而流向终点T的全部容量也是：

2+3=5

这说明网络存在达到5的潜在可能，但仅凭这些容量数字，还不能证明5一定可以实现。也许在网络中间存在某个隐藏的瓶颈。也许我们之前的分配方式并不合理。现在，真正的难题出现了：我们已经把一些货物送上了错误的路线，是否能够重新调整它们，让整个网络运得更多？

第四幕：最反直觉的一步——先把货物退回来

铁路编组站中的线路调整与货车重新编组。实际铁路的调度比静态流量模型复杂得多，但“重新分配已占用线路容量”的思想非常适合帮助理解残量网络。让我们回到刚才的第三次分配之后。当前流量为4。如果只允许货物继续沿既定方向前进，似乎已经无法改善。但问题在于：之前送出的流量，并不是永久不能改变的决定。我们可以减少某条线路已经分配的流量，再把腾出的容量交给其他路线。这与真正让火车物理倒车并不相同。在最大流数学模型中，它表示重新调整已经确定的运输计划。

一个隐藏在旧计划里的机会

观察A到B这条边。它的容量是2。当前也恰好使用了2。因为我们第一次沿：

S\rightarrow A\rightarrow B\rightarrow T

送出了2单位流量。但问题来了：为什么这2单位一定要经过A到B？实际上，A还有一条直接通往T的线路。

A\rightarrow T

它的容量为2，目前只使用了1。还剩1单位空间。如果我们把A到B的部分运输量减少1，再将这1单位改为直接由A送往T，会发生什么？A到B释放出1单位容量。同时，B所接收到的货物减少了1单位。但S到B这条线路，恰好还可以增加1。于是，一个新的完整调整方案出现了。从：

S\rightarrow B

增加1单位流量。在B处，将原来A到B的流量减少1。然后在A处，将A到T的流量增加1。这种调整可以表示为：

\boxed{S\rightarrow B\rightarrow A\rightarrow T}

等等。原来的网络不是只有：

A\rightarrow B

吗？怎么突然出现了：

B\rightarrow A

这条反方向的路？答案就是最大流算法最精妙的概念之一：反向边（Reverse Edge）。

B到A并不是一条真实新增的铁路

这是一条数学上用于调整流量的虚拟边。当原来的A到B已经分配了2单位流量时，我们就允许算法在残量网络中，从B向A退回最多2单位流量。这意味着：如果使用反向边B到A发送1单位调整量，真实网络中的变化是：

f(A,B)\leftarrow f(A,B)-1

原来：

f(A,B)=2

调整之后：

f(A,B)=1

它没有违反物理网络的方向限制。因为真实货物并没有突然从B逆着原来的单向铁路开回A。我们只是把之前安排在A到B上的1单位货物，重新分配到了另一条可行路线。

一次让整体流量变大的撤销操作

现在执行这条新的调整路径：

S\rightarrow B\rightarrow A\rightarrow T

它包含三段残余容量。第一段：

S\rightarrow B

还有1单位。第二段：

B\rightarrow A

是反向残量边，能够撤销最多2单位既有流量。第三段：

A\rightarrow T

还有1单位。因此，这条调整路径的最大增量是：

\boxed{\min(1,2,1)=1}

执行之后，五条真实边上的流量变为：

线路	调整前	调整后
S → A	3	3
S → B	1	2
A → B	2	1
A → T	1	2
B → T	3	3

新的总流量：

\boxed{|f|=5}

图37-4：反向边帮助重新安排运输

查看 SVG 配图原件

37-009-288b60ee8f25.svg · 点击查看大图

示意图仅突出第四次增广的变化。反向边B→A不是原网络中新建的运输线路，而是减少真实边A→B上既有流量的代数操作。

你可能会发现，这一步与普通的贪心算法非常不同。贪心算法往往先作出一个局部选择，然后继续向前。但最大流算法并不要求之前的每一次选择都永远保留。当发现更好的整体分配时，它允许调整原来的方案。这是一种非常重要的算法思想：已经作出的局部决策，只要能够以受控方式撤销，就不必成为阻碍全局最优的永久负担。而把这种思想明确表示为一张新网络，正是福特–富尔克森方法的重要突破。

第五幕：残量网络——让算法拥有重新选择的能力

残量网络的概念示意：正向边表示还能增加多少流量，反向边表示可以撤销多少先前分配的流量。不同状态下，残量网络会不断变化。所谓残量网络（Residual Network），是一个随着当前流量分配而改变的有向图。对于原网络中的一条边：

u\rightarrow v

假设容量为：

c(u,v)=5

当前已经使用了：

f(u,v)=3

那么，正向剩余容量就是：

\boxed{c_f(u,v)=5-3=2}

这表示还能沿原方向增加2单位流量。与此同时，在残量网络里还存在一条反向边：

v\rightarrow u

其可撤销容量为：

\boxed{c_f(v,u)=3}

这表示我们最多可以撤销原来安排的3单位流量。

图37-5：一条边在残量网络中的两种能力

查看 SVG 配图原件

37-011-457b2c96feb8.svg · 点击查看大图

原始边容量为5、当前流量为3。两种残量容量分别为2和3。

这是一种很巧妙的建模方式。我们不需要单独设计复杂的“撤销前一次决定”程序。只需要让算法在残量网络中寻找新的路径。如果经过一条正向残量边，就增加对应真实边的流量。如果经过一条反向残量边，就减少对应真实边的流量。于是，增量和撤销被统一到同一种操作中。

什么叫增广路径？

在残量网络中，如果存在一条：

S\rightsquigarrow T

的路径，并且路径上的每一条残量边都具有正的剩余容量，那么它就是一条增广路径（Augmenting Path）。这条路径能够让整个网络的流量继续增加。能够增加多少？由沿途最小的残量容量决定。如果一条路径经过的剩余容量为：

4,\quad7,\quad2,\quad5

那么最多只能增加：

\min(4,7,2,5)=2

单位。算法执行一次增广之后，会更新路径上所有边的流量和反向残量。然后重新寻找下一条增广路径。直到再也找不到从S通往T的残量路径。

福特–富尔克森方法的基本步骤

从零流量开始，所有真实边的初始流量设为0。
建立当前的残量网络，其中包含可增加的正向容量与可撤销的反向容量。
寻找一条从源点到汇点、全部残量容量为正的增广路径。
计算沿途的最小残量容量，沿路径增广这么多流量。
更新残量网络；重复，直到不存在增广路径。

这就是现代教材中常见的 Ford–Fulkerson 增广路径框架。这一方法在1955年12月29日的兰德报告中作了专门阐述，并发表于1957年《加拿大数学杂志》的论文：A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem。从史实上讲，我们应当区分：1954年研究报告、1956年期刊论文中的最大流最小割理论；以及1955年报告、1957年期刊论文中明确描述的一般增广路径算法。它们属于密切相关、逐步发展的研究成果，并不是完全相同日期完成的同一篇论文。^{[Cambridge Core][web.eecs.umich.edu][Paperzz]}

为什么沿着增广路径调整不会破坏守恒？

还记得中间节点的流量守恒吗？

\text{流入量}=\text{流出量}

假设一条增广路径经过中间节点A。那么沿路径增加

\Delta

单位流量时，A的一侧会得到相应的净流入变化，另一侧会产生等量的净流出变化。如果路径使用反向边，相关真实边的流量变化同样可以解释为撤销既有流量。只要更新规则正确，就不会凭空创造或消灭中间节点的货物。因此，沿完整增广路径调整之后：容量约束仍然成立。中间节点守恒仍然成立。而源点到汇点的总流量恰好增加

\Delta

。这就是算法每一步正确性的基础。但我们还没有解决最深的问题。如果再也找不到增广路径，为什么就能够确定已经达到全局最大值？仅凭“找不到新的路径”，还不足以让人完全信服。我们需要一个数学证明。而它将把最大流问题，引向一个看起来方向完全相反的问题：最小割。

第六幕：最小割——一道看不见的墙，决定整个网络的极限

水坝和狭窄水道展现了瓶颈容量的直观含义。对网络而言，真正限制整体输送能力的未必是一条边，而可能是一组跨越某种分割边界的连接。想象我们把整个网络分成两个部分。一边包含源点S。另一边包含汇点T。无论货物如何选择路线，只要想从S抵达T，就必须从第一部分跨越到第二部分。我们把这样的节点划分称为一个割（Cut）。

一道割，决定一个运输上界

假设我们选择：

U=\{S\}

剩下的节点构成：

V\setminus U=\{A,B,T\}

这意味着，我们在源点S与其他所有节点之间画出一条边界。从S这一侧穿越边界的线路只有两条：

S\rightarrow A

和：

S\rightarrow B

容量分别是3和2。所以，这道割的容量为：

c(U)=3+2=5

无论网络内部如何安排运输，源点S每单位时间最多只能把5单位流量送入网络。因此：

\boxed{|f|\le5}

这是一个不可突破的数学上界。而在上一幕中，我们通过四次增广，恰好构造出了：

|f|=5

于是：

\boxed{|f|_{\max}=5}

证明完成。我们不仅找到了一个能够输送5单位流量的方案。还证明了任何方案都不可能超过5。这两件事，必须同时成立，才能宣称已经找到最优解。

割并不只有一种

现在，把分界线换一个位置。令：

U=\{S,A,B\}

另一侧只有：

\{T\}

从U指向T的线路是：

A\rightarrow T,\quad B\rightarrow T

容量为：

2+3=5

所以，这同样是一道容量为5的割。但是，如果选择：

U=\{S,A\}

另一侧：

\{B,T\}

穿越边界的正向线路则是：

S\rightarrow B

A\rightarrow B

A\rightarrow T

容量之和：

2+2+2=6

由此可见，不同的割可以有不同容量。我们需要寻找的是其中容量最小的那一道。

图37-6：不同的网络切分，拥有不同的容量

分割 A

3+2=5

源点一侧只有S

分割 B

2+3=5

汇点一侧只有T

黄色虚线代表把节点分成两个集合的边界。割容量只统计从源点所在一侧指向汇点所在一侧的有向边容量。

现在，一个惊人的规律出现了。对于我们这个网络：

\text{最大流}=5

而：

\text{最小割容量}=5

这只是偶然吗？福特与富尔克森研究的核心结果告诉我们：并不是。对于满足通常条件的有限容量有向网络，总有：

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

这就是著名的最大流最小割定理（Max-Flow Min-Cut Theorem）。它是组合优化中极为重要的最大—最小关系。

为什么最大流永远不会超过任何一道割？

我们给出一个简洁的证明。假设节点集合被划分为：

U,\quad V\setminus U

其中S位于U，T位于另一侧。根据流量守恒，源点输出的净流量，必然等于从U向外输送的净流量。也就是：

|f|= \sum_{\substack{u\in U\\v\notin U}}f(u,v) - \sum_{\substack{v\notin U\\u\in U}}f(v,u)

第一项是向外穿越割的流量。第二项是从另一侧流回来的流量。由于流量非负，第二项不能使净输出增加。而第一项又不能超过每条边的容量总和。因此：

|f|\le \sum_{\substack{u\in U\\v\notin U}}c(u,v)

于是：

\boxed{|f|\le c(U)}

这对于任意一道合法的割都成立。所以，最大流必定不会超过最小割容量。但要证明两者一定相等，还需要进一步说明：为什么总能找到一个流量，恰好达到某道最小割的容量？答案又回到了残量网络。

当再也找不到增广路径时

假设我们已经执行了许多次增广。最后，在残量网络里，从S出发，再也无法到达T。我们把所有仍然可以从S通过正残量边到达的节点，放入集合

R

。其余节点放入另一侧。因为T不可达，所以：

S\in R,\qquad T\notin R

这构成一道割。现在，观察从R指向外侧的真实边。如果这些边中的某一条还有正向剩余容量，那么外侧对应的节点就可以从S到达。这与“它不在R中”矛盾。所以，从R向外的所有边必定已经满载。反过来，如果有一条从外侧进入R的真实边仍然具有正流量，那么它在残量网络中的反向边就具有正容量。这又意味着可以从R到达外侧节点。同样矛盾。所以，从外侧进入R的真实边必定没有正流量。因此，这道割上的净流量恰好等于割容量：

|f|=c(R)

而我们已经知道，任何流量都不能超过任何割容量。现在既找到了这样一份流，又找到了这样一道割，两者数值完全相同。那么它们必然分别是最大流和最小割。证明完成。这就是增广路径算法为什么具有正确性保证的核心。不存在增广路径，并不只是算法不知道下一步往哪里走，而是它已经找到了能够证明最优性的结构。从一张铁路地图，走到一道严密的数学定理。这一步，正是福特与富尔克森的研究之所以重要的原因。

第七幕：互动实验室——亲手把网络流量从4提升到5

最大流算法的可视化研究，通过逐步显示流量、增广路径和残量容量，帮助理解为什么某些局部决策必须被撤销。现在，我们已经拥有了算法所需的全部概念。源点。汇点。容量。流量守恒。增广路径。反向残量边。最小割。接下来，我们把它们组合在一起，亲手运行一次完整的 Ford–Fulkerson 算法。这个实验最重要的不是最终答案5。而是第四次增广。它会让你亲眼看到：为什么一个看似已经无法改进的流量分配，仍然可以通过撤销部分旧流量达到最优。

实验一：控制每一次增广

图37-7：最大流逐步实验室第 0 / 4 次增广

初始状态：所有线路都空闲

本次增广路径尚未选择增广路径

所有边上的流量均为0，源点还没有向终点送出任何货物。

当前总流量

0

本次增加流量

+0

三个需要认真观察的瞬间

第一，在第一次增广之后，A到B的线路已经满载。第二，在第三次增广之后，虽然总流量只有4，但仅沿原有线路的正方向已经找不到完整的新通路。第三，在第四次增广中，算法不是增加A到B的流量，而是减少它。观察这三个瞬间，就能够理解：一个最大流算法真正需要管理的，并不只是剩余的空闲容量。还包括那些可以通过修改原有分配重新获得的容量。这正是残量网络比原始网络更强大的原因。

实验二：改变容量，猜测最小割

现在尝试一个思考实验。假设我们把：

c(S,B)

从2增加到4。那么源点的总输出容量由5变成7。但汇点T的总输入容量仍然是：

c(A,T)+c(B,T)=2+3=5

因此，整个网络的最大流仍然不可能超过5。只扩充源点附近的容量，并不一定提高整体吞吐量。反过来，如果增加汇点入口容量，但源点出口仍然只有5，也同样无法突破5。这说明：要提高网络的整体能力，必须分析真正的瓶颈，而不是只扩建看起来最繁忙的线路。对于更复杂的网络，瓶颈可能由若干条分散的边共同组成。它们不一定都位于源点旁边。也不一定全部集中在汇点附近。最小割提供了一个从整体结构理解容量限制的数学工具。

第八幕：让计算机自己寻找增广路径

20世纪中期的科学计算机环境。随着存储程序计算机的发展，数学家能够将复杂的网络搜索过程写成可重复执行的算法。到现在为止，我们一直在用肉眼寻找路径。我们观察网络。判断还有哪些剩余容量。再决定下一次应该把流量往哪里送。但真实网络可能包含数千、数万甚至更多节点。它不可能依赖数学家一直盯着一张图。所以，我们需要让计算机自动完成这件事。所幸，第一季已经学习过一种非常合适的工具：图搜索。

使用广度优先搜索寻找道路

假设我们希望从S出发，寻找一条能够抵达T的增广路径。我们可以使用广度优先搜索（BFS）。先将S放入队列。然后依次检查所有尚未访问过、并且残量容量为正的相邻节点。如果发现T，就得到一条增广路径。如果队列耗尽，仍然无法到达T，就说明当前残量网络中不存在增广路径。算法可以停止。这样，我们就不必在复杂网络里依靠肉眼寻找路线。

从 Ford–Fulkerson 到 Edmonds–Karp

使用BFS寻找增广路径的做法，常被称为 Edmonds–Karp 算法。1972年，Jack Edmonds 与 Richard Karp 发表论文：Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems《网络流问题算法效率的理论改进》。他们研究了增广路径选择对算法运行效率的影响，并证明，始终选择边数最少的增广路径，可以得到明确的多项式时间复杂度保证。相关的最短增广路径思想及效率结果，也与1970年苏联数学家 Yefim Dinitz（Dinic）的独立研究有关。历史归属不能只写成1972年才第一次有人想到使用最短路径。^{[web.eecs.umich.edu][dblp]}对于采用BFS的 Edmonds–Karp 算法，经典时间复杂度为：

\boxed{O(VE^2)}

这里：

V=\text{节点数量}

E=\text{边数量}

这与不限定增广路径选择方式的 Ford–Fulkerson 框架有所不同。如果容量都是整数，且每次至少增加1单位流量，基本增广方法会在有限步内终止。但如果允许某些特殊实数容量，并采用不恰当的路径选择策略，基本 Ford–Fulkerson 方法可能出现无限增广而不终止的情况。而 Edmonds–Karp 通过规定最短增广路径的选择方式，获得了不依赖容量数值大小的多项式复杂度界限。这说明一个非常深刻的事实：对于同一个算法框架，怎样选择下一步，可能决定它能否拥有可靠的效率保证。

使用 Python 完整实现 Edmonds–Karp

下面，我们亲自编写一个最大流求解器。不依赖 NetworkX，也不依赖专门的优化软件。只使用 Python 标准库。


from collections import defaultdict, deque


def edmonds_karp(edges, source, sink):
    """
    edges: [(u, v, capacity), ...]
    返回: (最大流值, 最小割的源点侧节点集合)
    """

    residual = defaultdict(lambda: defaultdict(int))
    graph = defaultdict(set)

    # 建立残量网络
    for u, v, cap in edges:
        if cap < 0:
            raise ValueError("容量不能为负")

        residual[u][v] += cap

        # 反向边初始残量为0
        graph[u].add(v)
        graph[v].add(u)

    max_flow = 0

    while True:
        # BFS寻找增广路径
        parent = {source: None}
        queue = deque([source])

        while queue and sink not in parent:
            u = queue.popleft()

            for v in sorted(graph[u]):
                if v in parent:
                    continue

                if residual[u][v] <= 0:
                    continue

                parent[v] = u
                queue.append(v)

        # 已经找不到增广路径
        if sink not in parent:
            break

        # 计算路径瓶颈容量
        delta = float("inf")
        v = sink

        while v != source:
            u = parent[v]
            delta = min(delta, residual[u][v])
            v = u

        # 更新正向与反向残量
        v = sink

        while v != source:
            u = parent[v]

            residual[u][v] -= delta
            residual[v][u] += delta

            v = u

        max_flow += delta

    # 在最终残量网络中寻找源点可达的节点
    reachable = {source}
    queue = deque([source])

    while queue:
        u = queue.popleft()

        for v in graph[u]:
            if v not in reachable and residual[u][v] > 0:
                reachable.add(v)
                queue.append(v)

    return max_flow, reachable


edges = [
    ("S", "A", 3),
    ("S", "B", 2),
    ("A", "B", 2),
    ("A", "T", 2),
    ("B", "T", 3),
]

flow, source_side = edmonds_karp(
    edges, "S", "T"
)

cut_capacity = sum(
    cap
    for u, v, cap in edges
    if u in source_side and v not in source_side
)

print("最大流:", flow)
print("最小割容量:", cut_capacity)
print("最小割源点侧:", sorted(source_side))

assert flow == cut_capacity

程序运行后，应该得到：

最大流: 5
最小割容量: 5
最小割源点侧: ['S']

这个程序的最后一步很重要。它不仅输出最大流。还根据最终残量网络，找出从源点仍然可以到达的节点集合，并计算对应的割容量。如果最大流等于这道割的容量，就同时获得了最优解与最优性证据。与上一章的线性规划对偶证明类似，这种“找到一份可行解，再找到一份与其相等的上界证书”的思想，在组合优化中非常普遍。

为什么代码里的反向更新如此重要？

请观察这两行：

residual[u][v] -= delta
residual[v][u] += delta

第一行表示：沿当前增广路径使用了一部分残量容量。第二行表示：在反方向增加相应的可撤销容量。这是整个方法的关键。假设原网络里某条边容量为3。我们第一次沿正方向发送2单位流量。那么它的正向残量就减少2。而反向残量会增加2。如果未来发现需要重新分配，算法就能够通过反向残量边，撤销其中一部分旧流量。如果我们删掉第二行，算法将失去重新调整既有方案的能力。它可能像我们第四幕的第一次尝试那样，错误地停留在并非最优的状态。因此，残量网络不是一个可有可无的编程技巧。它是整个算法能够处理错误局部分配的核心机制。

第九幕：一张铁路图，为什么后来还能用于分配工作和处理图像？

计算机视觉中使用图割方法进行前景与背景分割的典型示意。某些图像分割模型能够转化为最小割问题，并通过最大流算法求解。1950年代，福特与富尔克森研究的是铁路网络的最大容量。但从数学上看，他们解决的是一个更加普遍的问题：当一个系统由节点与具有容量限制的连接构成，怎样在这些限制下找到最大可行流量？只要某项现实问题可以被转化为这样的网络，它就可能使用同一套理论。例如，给定一个任务分配问题。有三名工人：甲、乙、丙。有三项工作：A、B、C。每名工人最多只能承担一项工作。每项工作也只能由一人完成。甲能够做A或B。乙能够做B或C。丙只能做A。我们希望安排尽可能多的人完成不同工作。这看起来不像铁路运输。但它可以被转化为最大流问题。建立一个源点S。从S分别连接到三名工人，每条边容量为1。再从工人连接到能够完成的工作，每条边容量也为1。每项工作再连接到汇点T，容量同样为1。

图37-8：用最大流表示人员与任务匹配

查看 SVG 配图原件

37-018-21b421cd3d8f.svg · 点击查看大图

这个网络的最大流为3。对应的一组匹配是：

\text{甲}\rightarrow B

\text{乙}\rightarrow C

\text{丙}\rightarrow A

三个人全部获得任务。三项任务也全部完成。这里的每一单位流量，都可以理解为一项实际分配。这就是二分图匹配与网络流之间的重要联系。下一章，我们将进一步研究带有成本或收益的分配问题，以及匈牙利算法为什么能够在任务分配中找到整体最优方案。

从匹配走向图像

再看计算机视觉。一幅数字图像可以由大量像素或图像区域组成。假设我们希望将图像划分成前景与背景。一种建模方式，是给不同像素赋予倾向前景或背景的代价。同时，再为相邻像素分配相互分离时的代价。这样，我们希望找到一种分割方式：既符合像素本身的特征，又尽量避免产生不合理的局部边界。对于某些满足条件的图像能量模型，这个问题可以表示为最小割。再利用最大流最小割定理，便能通过网络流算法寻找最优分割。这种技术后来被用于图像分割、立体视觉、医学图像处理等领域。^{[Max-flow problem instances in vision][PubMed]}在这些应用里，网络的节点不再是城市。它们可能是像素。边也不再是铁路。而是像素之间的关系或分割代价。但是数学结构仍然与1950年代的网络流研究存在联系。

有些现实问题不能直接套用普通最大流

这里还需要补充一项重要限制。普通最大流主要处理的是：单一源点、单一汇点、边容量限制，以及中间节点的流量守恒。真实物流系统可能还包含运输时间、成本、车辆数量、时间窗和货物种类等条件。如果不同货物不能混在一起运输，或者多种货物共同竞争容量，那么可能需要多商品流模型。如果必须考虑每辆火车的运行时刻，可能需要动态网络流或更加复杂的调度模型。福特与富尔克森自己后来也研究过动态网络流和多商品流问题。例如，他们在1958年的论文中讨论了带有运输时间的动态流量问题。^{[Management Science][Operations Research]}所以，最大流不是解决所有物流问题的万能算法。它是一块重要的数学基础。只有当现实问题能够被准确表示为相应网络模型时，我们才能正确使用它。

尾声：真正的瓶颈，往往不在最显眼的地方

福特与富尔克森于1962年出版《Flows in Networks》。这部著作将最大流、网络运输及相关优化问题整理为系统的数学理论。^[JSTOR]让我们重新回到1950年代的兰德公司。一张铁路地图摆在研究人员面前。地图上有城市。有铁路。有不同线路的运输能力。研究者希望知道，整个系统究竟能够运输多少货物。最开始，这个问题似乎只需要不断向网络中增加流量。找到一条路。让它尽量满载。再找到下一条路。继续运输。但是，数学研究很快发现：事情并没有那么简单。一条看起来合理的路线，可能占用了其他路线更加需要的容量。某个中间节点已经无法继续发送货物，并不意味着整个网络不存在更好的分配方式。有时候，要让整个系统向前迈进，就必须先撤销一部分已经完成的分配。而福特–富尔克森方法最精妙的地方，就是将“增加流量”和“撤销旧分配”统一到了残量网络之中。算法不再把过去的选择当作不可改变的事实。它允许重新调整。允许修正。允许在局部决定不够理想时，寻找新的整体方案。最后，当整个残量网络中再也找不到一条增广路径时，数学又给了我们一项令人安心的保证。这不是因为计算机疲惫了。也不是因为它暂时没有想到其他办法。而是因为我们已经能够找出一道割。这道割的容量，恰好等于当前流量。任何其他可行方案，都无法超过这道割的容量。最优性于是得到了严格证明。这是一个非常美丽的数学结构。从一个方向看，我们在不断寻找更多能够运输的货物。从另一个方向看，我们在寻找整个网络无法突破的容量上限。当这两个数字相遇时：

\boxed{\text{最大流}=\text{最小割}}

整个问题便有了完整的答案。而这项发现，后来又产生了远远超出铁路运输的影响。在网络工程中，它可以帮助研究整体容量。在二分图匹配中，它可以帮助分配任务。在计算机视觉中，它可以帮助寻找图像分割方案。在更一般的组合优化中，它成为理解最大—最小定理、网络结构与最优性证明的重要入口。上一章，丹齐格教会我们：资源配置问题可以通过数学建模，转化为具有严格约束的最优化问题。这一章，福特与富尔克森又告诉我们：当问题拥有特殊的网络结构时，可以利用这种结构，设计出更加直接的算法。两项研究相互联系。又各自拥有独特的思想。单纯形法让我们学会在巨大的可行空间中寻找最优方案。最大流算法则让我们看到，某些最优问题的答案，可以由一条条路径不断改进，并最终由一道割加以证明。但整章最值得记住的，或许还是第四次增广的那一刻。我们已经将4单位货物送到了目的地。看上去，所有可用路线都已经被堵住。然后，算法做了一件违反直觉的事情。它没有盲目寻找更多新的线路。而是重新审视过去。将A到B的一单位旧流量撤销。让新的流量通过另一条路线。结果，整个网络的运输量从4提升到了5。一个局部的后退，最终带来了整体的前进。最好的算法，有时并不是永远坚持先前的选择，而是能够找到一种安全的方式，重新安排这些选择，使整个系统变得更好。而所谓瓶颈，也不一定是眼前最拥挤、最醒目的那条线路。它可能隐藏在整个网络的结构之中。只有理解了这张网络，才真正理解了它的极限。

历史档案：本章的事实依据

本章历史叙事主要依据原始论文、运筹学专业组织的传记资料，以及有关冷战铁路网络研究的数学史考证。

1956年：最大流最小割的早期论文Ford & Fulkerson — Maximal Flow Through a Network《Canadian Journal of Mathematics》第8卷，第399—404页。包含铁路问题的原始表述及最大流最小割定理。

1957年：增广路径算法的正式论文A Simple Algorithm for Finding Maximal Network Flows讨论寻找最大流的算法过程及其在运输问题中的应用。

数学史：冷战时期的铁路网络Alexander Schrijver — On the History of the Transportation and Maximum Flow Problems考证 Harris–Ross 报告、苏联铁路网络模型、研究的军事背景，以及早期最大流文献的时间差异。

人物档案：D. Ray FulkersonINFORMS：富尔克森生平与学术贡献介绍其研究生涯、兰德公司工作、与福特的合作，以及网络流领域的后续贡献。

1972年：网络流算法的效率改进Edmonds & Karp — Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems为最短增广路径策略的多项式复杂度分析提供重要依据。

本章中，铁路研究的历史背景、1950年代论文及重要人物有史料依据。四节点、五条边的网络，四次增广过程、残量网络动画与 Python 示例均为现代教学设计，并非福特与富尔克森的原始计算数据。关于 Harris–Ross 报告与早期兰德研究报告的日期矛盾，依照数学史考证保留不确定性。

下一章预告 · 第38章

《谁应该做哪份工作：匈牙利算法的诞生》

1955年，一位美国数学家开始研究人员与任务之间的最优分配。五个人。五项工作。每个人完成不同任务的效率都不一样。如果让每个人依次选择自己最擅长的工作，最终结果真的最好吗？一个局部看来最合理的选择，可能剥夺其他人更重要的机会。下一章，我们将认识 Harold Kuhn，并将故事追溯到更早的两位匈牙利数学家 Dénes Kőnig 与 Jenő Egerváry。从一张只有几行数字的分配表开始，我们将探索匈牙利算法如何帮助人类寻找整体最优匹配，以及为什么这项研究会在经济学、物流调度和计算机科学中产生深远影响。

——《算法的故事》第二季 · 第37章完

本章配图

第37章配图