Jeff Erickson 《Algorithms》10 -- 最大流&最小割

前言

　　我在学二分匹配时知道可以用最大流来解决问，但是也没去看过具体实现。也就是说这个知识点对我来说算是全新的，而且还要看全英文，还没开始我就已经觉得压力山大了。如果理解不当翻译不好，那以后再回来纠正吧。

知识点

在20世纪50年代中期，美国空军研究人员Theodore E. Harris和退伍将军Frank S. Ross写了一份研究连接苏维埃联盟和它的卫星国之间的铁路网络的机密报告。这个网络建模成一个图，44个顶点表示地理区域，105条边表示区域之间的铁路。每条边带有一个权值，表示区域之间材料运送的速率。根据总计和误差，他们断定了能从俄罗斯运送到欧洲的最大货物量和通过移除连接切断这个网络的最简方式（简单来说就是炸毁铁轨），他们称之为“瓶颈”。他们的报告以及网络图直到1999年才撤销保密。

　　这是有史以来第一次最大流和最小割问题的应用记录。对于两个问题，输入是一个有向图$G=(V,E)$，以及两个特殊顶点s和t，他们分别是源点和汇点。和上一章一样，我们使用$u\rightarrow v$表示从顶点u到v的有向边。直观上，最大流问题就是求从s到t运送资源的最大速率；最小割问题就是求可以切断s到t通路的最小代价。

流

(s,t)-flow（或者说就是指脱离上下文通过源点和汇点的流）是一个函数$f:E\rightarrow\mathbb{R}$对于除了s和t外的点满足以下守恒约束：

$\sum\limits_u f(u\rightarrow v)=\sum\limits_w f(v\rightarrow w)$

通俗来讲，就是进入v和离开v的流是相等的。为了简化概念，我们定义如果图中不存在边$u\rightarrow v$那么$f(u\rightarrow v)=0$。流$f$的值记作$|f|$,它是离开顶点s的网络流：

$|f|:=\sum\limits_w f(s\rightarrow w)-\sum\limits_u f(u\rightarrow s)$

　　不难证明$|f|$与流入汇点的网络流相等。为了简化概念，用$\partial f(v)$表示离开任意顶点v的网络流

$\partial f(v):=\sum\limits_u f(u\rightarrow v)-\sum\limits_w f(v\rightarrow w)$

守恒约束意味着对于除了s和t的每个顶点v都有$\partial f(v)=0$，所以

$\sum\limits \partial f(v)= \partial f(s)+\partial f(t)$

另外，任意流离开一个顶点后一定会进入另一个顶点，所以我们一定有$\sum_v \partial f(v)=0$。接着就得到了$|f|=\partial f(s)=-\partial f(t)$。
　　现在假设我们有另外一个函数$c:E\rightarrow\mathbb{R}_{\geq 0}$表示对于每条边e的非负容量$c(e)$。我们说一个流f是可行的仅当对于每条边$0\leq f(e)\leq c(e)$。大多数时候我们只讨论基于确定容量函数c的可行流。当$f(e)=c(e)$时我们称流f浸满了边e，当$f(e)=0$我们称e为避开边。最大流问题就是是计算在带有容量函数的有向图中值最大的可行(s,t)-flow。

割

(s,t)-cut（或者说就是指脱离上下文通过源点和汇点的割）是将顶点分为两个相交集合S和T的分割—这表示$S\cup T=V$并且$S\cap T=\varnothing$—其中$s\in S$，$t\in T$。
　　如果我们有一个容量函数$c:E\rightarrow\mathbb{R}_{\geq 0}$，一个割的容量就是从S到T的所有边的容量和：

$||S,T||:=\sum\limits_{v\in S}\sum\limits_{w\in T}c(v\rightarrow w)$

（如果图中不存在$v\rightarrow w$，我们再次假设$c(\rightarrow w)=0$）注意这个定义是对称的；从T到S的边是不重要的。最小割问题就是容量最小的(s,t)-cut。

　　直观上，最小割是一种破坏从s到t的所有流的代价最小的方式。确实，不难看出流和割的以下关系：
引理10.1.用$f$表示任意可行的(s,t)-flow，$(S,T)$表示任意(s,t)-cut。$f$的值不超过$(S,T)$的容量。甚至$|f|=||S,T||$当且仅当$f$浸满了每条从S到T的边并且避开了每条从T到S的边。

证明：选择一对你中意的流$f$和割$(S,T)$，接着看下面的不等式推导：

$\begin{align}|f|&=\partial f(s) &[定义]&\\&=\sum\limits_{v\in S}\partial f(v) &[守恒约束]& \\ &=\sum\limits_{v\in S}\sum\limits_{w}f(v\rightarrow w)-\sum\limits_{v\in S}\sum\limits_{u}f(u\rightarrow v) &[\partial 定义]& \\&=\sum\limits_{v\in S}\sum\limits_{w\notin S}f(v\rightarrow w)-\sum\limits_{v\in S}\sum\limits_{w\notin S}f(u\rightarrow v) &[移除从S到S的边]& \\ &=\sum\limits_{v\in S}\sum\limits_{w\in T}f(v\rightarrow w)-\sum\limits_{v\in S}\sum\limits_{w\in T}f(u\rightarrow v) &[割定义]& \\ &\leq \sum\limits_{v\in S}\sum\limits_{w\in T}f(v\rightarrow w) &[因为f(u\rightarrow v)\geq 0]& \\ &\leq \sum\limits_{v\in S}\sum\limits_{w\in T}c(v\rightarrow w) &[因为f(u\rightarrow v)\leq c(v\rightarrow w)]& \\ &=||S,T|| &[定义]& \end{align}$

以上推导式中：在第二步，因为对于$v\in S\{s\}$有$\partial f(v)=0$，我们就是在加零。在第四步，我们移除了x、y都在S中的流$f(x\rightarrow y)$的值，因为它在两个求和中都存在，当v=x、w=y它为正，当v=y、u=x它为负。
　　而且推导中第一个不大于关系式要变成等于当且仅当$f$避开了所有从T到S的边。类似地第二个不大于关系式要变成等于当且仅当f浸满了所有从S到T的边。

这个引理说明如果$|f|=||S,T||$，那么$f$一定是一个最大流，并且$(S,T)$一定是一个最小割。

最大流-最小割定理

每个流网络中都存在一个可行流(s,t)-flow $f$和一个(s,t)-cut $(S,T)$，并且$|f|=||S,T||$。这就是著名的最大流-最小割定理，它在1954年被Lester Ford和Delbert Fulkerson首次证明。

最大流-最小割定理：在每个带有源点s和汇点t的流网络中，最大流(s,t)-flow的值等于最小割(s,t)-cut的容量。

　　Ford和Fulkerson如下证明这个定理。假设一个图G，顶点s和t，容量函数$c:E\rightarrow\mathbb{R}_{\geq 0}$。如果我们假设G是以简化的（任意两个点u和v之间最多一条边），证明起来会更容易。换句话说，要么$c(u\rightarrow v)=0$，或者$c(v\rightarrow u)=0$。这个假设很容易实现：在每条边$u\rightarrow v$中插入新顶点x，用路径$u\rightarrow x\rightarrow v$代替边$u\rightarrow v$，然后定义$c(u\rightarrow x)=c(x\rightarrow v)=c(u\rightarrow v)$。修改后的图与原图有着同样的最大流值和最小割容量。

　　已知$f$是G中的任意一个可行的(s,t)-flow。我们定义一个新的容量函数$c_f:V\times V\rightarrow\mathbb{R}$，称之为剩余容量（后面我就简称“余量”了），如下：

$\begin{equation}c_f(u\rightarrow v)=\begin{cases}c(u\rightarrow v)-f(u\rightarrow v) &if\ u\rightarrow v\in E \\ f(v\rightarrow u) &if\ v\rightarrow u\in E \\ 0 &otherwise \end{cases}\end{equation}$

直观上，一条边的余量表示这条边当前还能通过多大值的流。因为$f\geq 0$和$f\leq c$，这些余量永远是非负的。有可能原图不存在边$u\rightarrow v$，但是有$c_f(u\rightarrow v) > 0$的情况。这样我们定义余量图$G_f=(V,E_f)$，$E_f$是一个边的集合，这些变得的余量都是正的。大多数余量图都是非简化的；特别是当$0<f(u\rightarrow v)<c(u\rightarrow v)$，那么余量图$G_f$中同时包含了边$u\rightarrow v$及其反向边$v\rightarrow u$。

　　现在我们有两种情况要考虑：余量图$G_f$中存在一条从源点s到汇点t的有向路径，或者它不存在。
　　首先假设余量图$G_f$包含一条从s到t的有向路径P；我们称P为增广路径。用$F=min_{u\rightarrow v\in P} c_f(u\rightarrow v)$表示我们能从P中通过的最大流量。我们定义一个新的流$f’:E\rightarrow\mathbb{R}$（在原图中）如下：

$\begin{equation}f'(u\rightarrow v)=\begin{cases} f(u\rightarrow v)+F &if\ u\rightarrow v\in P \\ f(u\rightarrow v)-F &if\ v\rightarrow u\in P \\ f(u\rightarrow v) &otherwise \end{cases}\end{equation}$

　　我们称这个新流$f’$对于原容量c也是可行的，这表示在任何地方都有$0\leq f’\leq c$。假设原图中的一条边$u\rightarrow v$，存在三种情况需要考虑。
　　• 如果增广路径P包含了$u\rightarrow v$，那么

$f'(u\rightarrow v)=f(u\rightarrow v)+F>f(u\rightarrow v)\geq 0$

因为f是可行流，并且

$\begin{align}f'(u\rightarrow v)&=f(u\rightarrow v)+F &f'定义&\\ &\leq f(u\rightarrow v)+c_f(u\rightarrow v) &F定义& \\ &=f(u\rightarrow v)+c(u\rightarrow v)-f(u\rightarrow v) &c_f定义& \\ &=c(\rightarrow v)\end{align}$

　　• 如果增广路径P包含了反向边$v\rightarrow u$，那么

$f'(u\rightarrow v)=f(u\rightarrow v)-F<f(u\rightarrow v)\leq c(u\rightarrow v)$

又是因为f是可行流，并且

$\begin{align}f'(u\rightarrow v)&=f(u\rightarrow v)-F &f'定义&\\ &\geq f(u\rightarrow v)-c_f(v\rightarrow u) &F定义& \\ &=f(u\rightarrow v)-f(u\rightarrow v) &c_f定义& \\ &=0\end{align}$

　　• 最后，如果增广路径既不通过$u\rightarrow v$也不通过$v\rightarrow u$，那么$f’(u\rightarrow v)=f(u\rightarrow v)$，因为$f$是可行流，有$0\leq f’(u\rightarrow v)\leq c(u\rightarrow v)$。

所以$f’$也是可行流。
　　最后，增广路径中只有第一条是从s离开的，这表示$|f’|=|f|+F>|f|$。这样，$f’$是一个比$f$更大的可行流。我们得出如果在余量图$G_f$中存在从s到t的路径，那么$f$就不是最大流。

　　另外，假如余量图$G_f$不包含从s到t的有向路径。S表示$G_f$中可以从s到达的顶点，那么T=V\S。(S,T)无疑就是一个(s,t)-cut。对于每个顶点$u\in S$和$v\in T$，我们有

$c_f(u\rightarrow v)=(c(u\rightarrow v)-f(u\rightarrow v))+f(v\rightarrow u)=0$

$f$是可行流表明$c(u\rightarrow v)-f(u\rightarrow v)\geq 0$并且$f(v\rightarrow u)\geq 0$，所以事实上我们一定有$c(\rightarrow v)-f(u\rightarrow v)=0$并且$f(v\rightarrow u)=0$。换句话说，我们的流$f$浸满了每一条从S到T的边而且避开了每一条从T到S的边。引理10.1表明
现在$|f|=||S,T||$，这意味着$f$是一个最大流并且$(S,T)$是一个最小割。

　　这样证明就完成了。

Ford和Fulkerson的增广路径算法

Ford和Fulkerson的最大流-最小割定理暗示了一个计算最大流的算法：以一个值为零的流开始，不断地从余量图中寻找任意路径来增大当前流，直到没有这样的路径存在。
　　这个算法有一个重要且明显的推论：

完整性定理. 如果流网络的容量都是整数，那么存在一个最大流，它通过的每一条边都是一个整数。

证明： 我们基于增广路径算法的每次迭代后的情况来做归纳，所有流的值和所有的余量都是整数。
• 在第一次迭代之前，当前流的值是0（这是一个整数）,所有余量都是原来的原来的容量，根据定义此时余量都是整数。
• 再往后的每次迭代中，有归纳假设可知增广路径的容量F是一个整数，所以增广后改变每一条边上的流，以及每一条边的余量，也是一个整数。
尤其是，增广路径算法的每次迭代后流的值都会增加一个正整数。接着这个算法最终停止返回一个最大流。

　　如果每条边的容量都是一个整数，适当的，Ford-Fulkerson算法最多经过$|f^{*}|$次迭代，$ f^{*}$就是一个最大流。在每次迭代中，我们可以构造余量图$G_f$并且在$O(E)$时间内执行一个任意优先搜索找到增广路径。这样，在这个设置下，此算法的最坏运行时为$O(E|f^{*}|)$。

　　Jack Edmonds和Richar Karp观察到这个运行时会高于实际分析。假设有一个4节点网络如上图，X是一个超大的整数。这个网络中的最大流明显是$2X$。然而Ford-Fulkerson也许会交替在增广路径$s\rightarrow u\rightarrow v\rightarrow t$和$s\rightarrow v\rightarrow u\rightarrow t$中推入一个单元流，导致运行时达到$\Theta(X)=\Omega(|f^{*}|)$。
　　Ford和Fulkerson的算法在实践中中通常还是算快的，尤其是在最大流值$|f^{*}|$较小的情况下，但是如果没有进一步地限制增广路径，最坏情况下这个算法并不是高效地。Edmonds和Karp的特殊网络案例描述起来只需要$O(logX)$字节；这样，Ford-Fulkerson算法的运行时实际上是输入大小的指数级。

无理数容量

但是如果容量并不都是整数呢？如果我们将所有容量都乘一个正的常量，每一个地方的最大流都会增大一个同样的常量因子。也就是说如果所有的边容量都是有理数，那么Ford-Fulkerson算法最终会停止，尽管任然需要指数级的时间（相对于描述输入的空间大小）。
　　然而，如果我们允许无理数容量，这个算法可以无限循环下去，一直找到越来越小的增广路径。更糟的是，这个增广的无限序列不会收敛于最大流，或者甚至连最大流的分数部分都不是！Uri Zwick在1993年找到了一个网络展现了这个糟糕的情况。

　　假设一个6节点的网络如上图。九条边中有六条是超大整数容量$X$，两条的容量是1，还有一条的容量是$\phi=(\sqrt{5}-1)/2\approx 0.618034$，选择这个容量是因为$1-\phi=\phi^2$。为了证明Ford-Fulkerson算法会卡住，我们可以观察在算法过程中三条水平边的余量。（其他六条边的余量总是不小于$X-3$）
　　假设Ford-Fulkerson算法选择上图中间的增广路径作为开始。三条水平边，从左到右，现在的余量是$1,0,\phi$。归纳假设当前三条水平边的余量是$\phi^{k-1},0,\phi^k$，k为任意正整数。

通过增广路径B，流的值增加$\phi^k$；现在的余量是$\phi^{k+1},\phi^k,0$。
通过增广路径C，流的值增加$\phi^k$；现在的余量是$\phi^{k+1},0,\phi^k$。
通过增广路径B，流的值增加$\phi^{k+1}$；现在的余量是$0,\phi^{k+1},\phi^{k+2}$。
通过增广路径A，流的值增加$\phi^{k+1}$；现在的余量是$\phi^{k+1},0,\phi^{k+2}$。

也就是说通过归纳法在$4n+1$次增广操作后，水平边的余量是$\phi^{2n-2},0,\phi^{2n-1}$，随着增广的次数趋于无穷，流的值收敛于

$1+2\sum\limits^\infty_{i=1}\phi^i=1+\frac{2}{\phi}=2+\sqrt{5}<5$

（注：上面的关系式和原书不一致，我令$F_n=\sum^\infty_{i=1}\phi^i$，再推出$F_n-\phi F_n=\phi$，之后的推导结果就有分歧了，不过影响不大。）
如此明显可以看出最大流的值$2X+1\gg 5$。

　　务实的读者会发现，为什么要关注无理数容量呢；毕竟，计算机只能准确表示证书或者有理数。好问题！数学家的答案是限制整数容量就是人为的；它是数字计算硬件的产物（或者也许是其他不相关的物理法则），并不是抽象计算问题的固有特征。但是一个更实际的原因是此算法的无理数输入行为告诉我们在实际情况中有时候浮点容量会带来一些造成一些糟糕的情况！即使是非常合理的容量，在Ford-Fulkerson算法的算法实现过程中稍有不慎也会导致无限循环，因为一些简单的舍入失误，也会导致偏离正确答案。

流的分解与聚合

流是通常会被定义为通过图中一些满足确定约束的顶点和边的函数。然而，流在确定的上下文中有一个更自然且好用的第二特征。
　　考虑一个带有源点s和汇点t的任意图$G$。假设任意两个(s,t)-flow $f$和$g$，以及任意两个实数$\alpha$和$\beta$，还有函数$h:E\rightarrow\mathbb{R}$定义如下：

$h(u\rightarrow v):=\alpha\cdot f(u\rightarrow v)+\beta\cdot g(u\rightarrow v)$

对于每条边$u\rightarrow v$；我们将这个定义简化为$h=\alpha f+\beta g$。根据定义可以直接得出h也是一个(s,t)-flow，值为$|h|=\alpha |f|+\beta |g|$。普遍来说，任意(s,t)-flow的线性叠加也是一个(s,t)-flow。
　　事实证明任意(s,t)-flow可以被写成一个特殊结构的权值和。对于任意从s到t的有向路径P，我们定义相应的路径流，设置如下：

$\begin{equation}P(u\rightarrow v)=\begin{cases}1 & if\ u\rightarrow v\in P \\ -1 & if\ v\rightarrow u\in P \\ 0 & otherwise\end{cases}\end{equation}$

由定义可知函数$P:E\rightarrow\mathbb{R}$确实一个值为1的(s,t)-flow。这里我们故意让变量P即表示路径又表示通过该路径的单元流。
　　类似地，对于任何一个有向环C，我们定义相应的环流，设置如下：

$\begin{equation}C(u\rightarrow v)=\begin{cases}1 & if\ u\rightarrow v \in C \\ -1 & if\ v\rightarrow u\in C \\ 0 & otherwise\end{cases}\end{equation}$

　　接着，验证函数$C:E\rightarrow\mathbb{R}$是值为0的(s,t)-flow就很简单了。
　　我们前文的论证表明任意路径流和环流的线性叠加后变成了另外一个流；这个权值求和也称作流聚合。此外，每个非负流都有一个如下特殊结构的流分解。

流分解定理. 每一个非负的(s,t)-flow $f$ 可以被写成是非负的有向路径和有向环的线性叠加。此外，一条有向边$u\rightarrow v$出现在这些路径或者环的其中之一当且仅当$f(u\rightarrow v)>0$，并且路径和环的数量不会超过这个网络中边的数量。

证明： 通过归纳法我们基于非负流中边的数量来证明此定理，直接逆向执行Ford-Fulkerson算法。只要至少有一条图中的边带有非负流，我们就可以找到一条带有流的(s,t)-path或者一个有向环。尽量从路径和环中减去流直到只剩一条边，然后归纳法可以给出我们剩下的分解。

　　为了形式化论证，我们先考虑复合环流（circulation）的特殊情况；假设路径中流的值为0，所有的流都保存在顶点中。假设任意流网络中的一个任意复合环流$f$，用 $\sharp f$ 表示边$u\rightarrow v$且$f(u\rightarrow v)>0$的数量。我们证明$f$可以被分解为不超过$max\{0,\sharp f-1\}$个非负环的线性叠加，基于$\sharp f$归纳。有以下三种情况需要考虑：
　　• 如果$\sharp f=0$，那么$f$明显是0个环的线性叠加。
　　• 假设对于任意一个简单有向环的边$u\rightarrow v$有$f(u\rightarrow v)>0$。那么$\sharp f\geq 2$，并且毋庸多言$f$是一个有向环的线性叠加。
　　• 相反，选择一个任意边$u\rightarrow v$并且$f(u\rightarrow v)>0$。假设一个任意通路$v_0\rightarrow v_1\rightarrow v_2\rightarrow \cdot\cdot\cdot$，$v_0=u$且$v_1=v$，如此对于任意索引i都有$f(v_{i-1}\rightarrow v_i)>0$。守恒约束表明每个顶点有流进入就有流离开，所以我们可以随意设定这个通路的长度；尤其是，这个通路最终一定会到达同一顶点超过一次。用k表示对于任意$j<k$满足$v_j=v_k$的最小索引。子通路$v_j\rightarrow v_{j+1}\rightarrow \cdot\cdot\cdot\rightarrow v_k$是一个简单有向环C。
　　定义$F:=min_{e\in C} f(e)$，然后假设一个函数$f’:=f-F\cdot C$，或者更啰嗦的表示为：

$\begin{equation}f'(u\rightarrow v):=\begin{cases}f(u\rightarrow v)-F & if\ u\rightarrow v\in C \\ f(u\rightarrow v) & otherwise\end{cases}\end{equation}$

有定义可知$f’$是G中另外一个可行的复合环流。C中至少存在一条边$e\in C$并且$f(e)=F$，因此$f’(e)=0$，也就是说$\sharp f’\leq \sharp f-1$。因为$f’$中带有流的边比$f$少，归纳法最多能把$f’$分解成$\sharp f’-1\leq \sharp f-2$个环。将F个单元流加入环C就得到了f的流分解；简介表示为：$f=f’+F\cdot C$。

现在用$f$表示任意流网络中的任意一个(s,t)-flow，如此就有$|f|>0$。添加一条边$t\rightarrow s$到网络中，并且通过设置$f’(t\rightarrow s)=|f|$，对于原图中的所有边$u\rightarrow v$有$f’(u\rightarrow v)=f(u\rightarrow v)$，定义一个复合环流$f’$；可以看出$\sharp f’=\sharp f+1\geq 2$。前面的论证说明复合环流$f’$最多由$\sharp f’-1$个环线性叠加而成。删除边$t\rightarrow s$可知原始流$f$最多可以分解成$\sharp f’-1=\sharp f$个路径和环的线性叠加。特别是，$f’$中包含$t\rightarrow s$的环变成了$f$中的(s,t)-path，而$f’$中不包含$t\rightarrow s$的环在$f$中保持不变。

　　流分解定理的证明得到了两个特殊情况的强效结论。
　　• 任意复合环流可以被分解为环的权值求和；不需要任何路径。
　　• 任意有向无环的(s,t)-flow可以被分解为(s,t)-path的权值求和；不需要任何环。
此外，通过去除所有环流，我们可以将任意流转化成一个值相同的有向无环流。尤其是，每个流网络都有都有一个有向无环的最大(s,t)-flow。
这个证明可以直接转化出一个算法，类似于Ford-Fulkerson，将任意(s,t)-flow分解出任意路径和环。这个算法重复地在剩余流中找到一个有向的(s,t)-path或者有向环，然后从其中减去这些路径或环中的流，直到剩余流为空。我们可以在O(V)时间内找到一个路径流或者环流：

　　• 如果任意边从s离开是带有非负流，在流图中由一条任意通路从s出发直到它到达t（找到一个流路径）或者二次到达同一顶点（找到一个流环路）。
　　• 如果没有非负流从s离开，找到任意一个出流为正的顶点v，在流图中由一条任意通路从s出发二次到达同一顶点（找到一个流环路）。

两种情况下，由守恒约束可知这个算法永远不会卡住。每次迭代需要$O(V)$的时间并且从流图中至少移除一条边；这样，整个分解算法的运行时为$O(VE)$。
　　流分解提供了一个运行时更低的最大流算法，每次构造一个流路径或者流环路。每个流都可以被分解成最多E个路径和环，其中每个都不能超过V条边，所以总的来说流分解的复杂度是$O(VE)$。这样，任何最大流算法明确地一次构造一个流路径或者流环路—尤其是，任何Ford和Fulkerson的增广路径算法—最坏情况下的流分解次数为$\Omega(VE)$。

Edmonds和Karp的算法

Ford和Fulkerson的算法没有指出如何选择余量图中的增广路径；最坏运行时的最坏情况恰恰取决于如何选择增广路径。在1970年代早期，Jack Edmonds和Richard Karp发表了两个选择增广路径的规则，两者都可以实现高效算法。

最大增广路径

Edmonds和Karp首次提出这个贪心算法时基于以下规则：选择当前瓶颈值最大的增广路径。
在有向图中找出最大瓶颈的(s,t)-path使用“最佳优先”遍历可以在$O(E logV)$时间内做到，类似于Jarnik的最小生成树算法或者Dijkstra的最短路径算法。这个算法增长一棵有向树T，根节点是s，一次增加一个顶点，通过重复的寻找离开T的最高容量的边并加入T中，直到T包含了一条从s到t的路径。或者，模仿Kruskal的算法—以容量递减的顺序一次插入一条边直到有一条从s到t的路径—尽管这个方法在有向图中的效率不高。
　　为了完成这个流算法的运行时分析，我们需要一个算法停止前的迭代次数上界。事实上，对于任意实数容量，这个算法可能不会停止；对于整数容量，虽然我们可以通过最大流值$f^{*}$确定迭代次数，如下。
　　用$f$表示G中的任意流，$f’$表示当前余量图$G_f$的最大流。（在算法开始之时，$G_f=G$并且$f’=f^{*}$）。我们已经证明过$f’$可以被分解为最多E个路径和环。一个简单的平均论证表明在这个分解中至少有一个条路径携带了不少于$|f’|/E$的单元流。也就是说$G_f$中的最大的(s,t)-path携带了不少于$|f’|/E$个单元流。
　　这样，沿着$G_f$中的最大瓶颈流每次最少变为原来的$1-1/E$。换句话说，剩余的最大流随着迭代次数呈指数级衰减。经过$E\cdot ln|f^{*}|$次迭代，$G_f$中的最大流值不超过

$\begin{align}|f^{*}|\cdot (1-1/E)^{E\cdot ln|f^{*}|} &=|f^{*}|\cdot e^{E\cdot ln(1-1/E)\cdot ln|f^{*}|} <|f^{*}|e^{-ln|f^{*}|}=1\end{align}$

（式中e是自然常数不是边）注意式中第一个不等关系，需要求$E\cdot ln(1-1/E)$与常数-1的关系，此处令$f(E)=E$和$g(E)=ln(1-1/E)$，当E趋于无穷大时，$f(E)$趋于无穷大，$g(E)$趋于0。使用洛必达法则求导：

$(E\cdot ln(1-1/E))'=(\frac{ln(1-1/E)}{1/E})'=\frac{\frac{E}{E-1}\cdot \frac{1}{E^2}}{-\frac{1}{E^2}}=-\frac{E}{E-1}$

由上式可知$E\cdot (1-1/E)$的极限趋于-1。
在$E\cdot ln|f^{*}|$次迭代后，余量图中的最大流已经小于1。如果所有的容量都是整数，如果余量图中最大流，那它的值一定是0；换句话说$f$就是一个最大流。
　　我们得出对于带有整数容量的图，Edmonds-Karp的最大路径算法运行时为$O(E^2logV log|f^{*}|)$。不像原来的Ford-Fulkerson算法，这个时间边界的确是输入大小的多项式级。
　　正如原来的Ford-Fulkerson算法，最大路径算法也会在带有实数容量的网络中陷于无限循环。然而我们的分析表明即使算法不会停止，但它得到的流$f$无限接近真实的最大流。

最短增广路径

第二个Edmons-Karp规则实际上应该是在Ford-Fulkerson最大流初稿中左右实践启发提到的；这个规则的一种变体又在1970年被俄罗斯数学家Yefim Dinitz独立提出。
选个当前边最少的增广路径。
使用广度优先搜索可以在$O(E)$时间内在余量图中找到最短增广路径。令人惊讶的是这个算法在多项式级次数迭代后停止，而不依赖于于实际边的容量。
　　这个多项式级的上界证明依赖于两个余量图变化的两种情况。用$f_i$表示当前流经过了i次增广，$G_i$表示对应的余量图。特别是，$f_0=0$并且$G_0=G$。对于每个顶点v，用$level_i(v)$表示在$G_i$中从s到t的无权最短距离，或者换个说法，v在$G_i$中根节点为s的广度优先搜索树的层级。需要注意，如果在$G_i$中没有从s到v的路径，那么$level_i(v)=\infty$。
　　我们首先观察的时一个顶点的层级只会随着增广次数的增加而增加。

引理10.2. 对于所有的顶点v和整数$i>0$都有$level_i(v)\geq level_{i-1}(v)$。

证明： 假设一个任意的正整数$i>0$和一个任意的顶点v。我们基于$level_i(v)$来归纳证明。假设对于所有的$level_i(u)<level_i(v)$的顶点u，都有$level_i(u)\geq level_{i-1}(u)$。有三种情况需要考虑。
• 如果$v-s$，我们马上得到$level_i(s)=level_{i-1}=0$。
• 如果$G_i$中不存在从s到v的路径，那么$level_i(v)=\infty\geq level_{i-1}(v)$
• 相反，假设$s\rightarrow \cdot\cdot\cdot\rightarrow u\rightarrow v$是$G_i$中从s到v的无权最短路径。因为这是一个最短路径，我们得到$level_i(v)=level_i(u)+1$，所以归纳假设表明$level_i(u)\geq level_{i-1}(u)$。为了完成这个证明，我们需要推理出$level_{i-1}(u)\geq level_{i-1}(v)-1$。我们有两种子情况需要考虑。

如果$u\rightarrow v$是$G_{i-1}$中的边，那么$level_{i-1}(v)\leq level_{i-1}(u)+1$，因为层级室友广度优先遍历定义的。
否则，$u\rightarrow v$不是$G_{i-1}$中的边，那么它的反向边$v\rightarrow u$一定是第i条增广路径，根据定义这条反向边是$G_{i-1}$中从s到t的无权最短路径。也就是说$level_{i-1}(v)=level_{i-1}(u)\leq level_{i-1}(u)+1$。
在两种子情况中，都得到了$level_i(v)=level_i(u)+1\geq level_{i-1}(u)+1\geq level_{i-1}(v)$。

　　我们在增广当前流时，增广路径中的瓶颈边会从余量图中消失，并且某些边又会因为增广路径的翻转再次出现。我们接着观察的时一条边不会消失或者出现太多次。

引理10.3. 在执行Edmonds-Karp最短增广路径算法的过程中，每条边$u\rightarrow v$最多从余量图$G_f$中消失$V/2$次。

证明： 假设$u\rightarrow v$在余量图$G_i$和$G_{j+1}$中存在，但是在中间余量图$G_{i+1},…,G_j$中不存在，且所有$i<j$。那么$u\rightarrow v$一定在第i条增广路径中，所以$level_i(v)=level_i(u)+1$，并且$v\rightarrow u$一定在第j条增广路径中，所以$level_j(v)=level_j(u)-1$。由上一条引理可知

$level_j(u)=level_j(v)+1\geq level_i(v)+1=level_i(u)+2$

换句话说，在$u\rightarrow v$的消失与出现之间，从s到u的距离最少增加2。因为每个层级都是少于V或者等于无穷的，那么消失的次数最多是$V/2$。

　　现在我们可以得出迭代次数的上界。因为每条边最多消失$V/2$次，总的消失次数是$EV/2$。但是每次迭代至少消失一条边，这个算法最多迭代$EV/2$次。最终，每次迭代的耗时为$O(E)$，算法总耗时为$O(VE^2)$。

进一步发展

到此最大流算法的故事还没有结束。在几十年的长远研究中出现过一些快速算法，下图做了一些总结。所有列出的算法都列出了运行时。大多数算法有两种变体：一种是每次迭代都执行暴力求解，另一种更快的变体则是使用负载的数据结构来维护流网络的生成树，所以每次迭代的执行时间都是对数级的；实际上，最大流任然是非常活跃的研究领域。

　　已知最快的最大流算法是James Orlin在2012年发布的，运行时为$O(VE)$，精确到流分解的最坏情况。Orlin算法的详情是超出本书范围的；使用的是他自己的新技术，Orlin还使用了几个较老的算法和数据结构作为黑盒子，它们本身都已很复杂了。特别是，Orlin算法并没有清楚地构造流的分解；事实上，对于只有$O(V)$条边的图，他的扩展算法的实际运行时只要$O(V^2/logV)$。不管怎么说，为了方便最大流算法的运行时评估，这个时间界限还是需要留意的。所以每当你看到相关问题，请记住：在O(VE)时间内计算出最大流是可行的。

结语

手都快断了，终于翻译完了。本文难度稍大，阅读过程中我去找了好几篇中文博客来辅助理解。主要还是有些概念完全摸不到边，读了几遍还是不懂。比如说反向边这个概念，当时我就想不明白为什么原图需要简化成两点之间不超过一条边，而余量图又不是；还有就是本文没给出增广路径的明确概念，而我对此的理解又仅限于二分图，想着想着就跑偏了；再有就是一些数学推导，别人公式一步就过去了，我还在大费周章地做代数运算。

原文链接

http://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf