网络流
本文最后更新于 2026年6月14日 下午
北京大学信息科学技术学院
算法设计与分析(2026春)的课程笔记
第七章：网络流
终于要尝试更新网络流了，这一章的ppt可谓是抽象中的抽象，本身定义多多，算法也复杂无比，第一次看时完全懵住，希望今晚我能尽量把它整理清楚www
最大流问题
网络流及其性质
ppt上一开始便是给出形式化抽象定义，让人一头雾水
我们先看生活中的一个例子，考虑A地到B地的公路网络，中间存在若干个收费站和岔路口，每段路都有限定的车流量，除AB两地外，每一个中间点都不允许滞留，也不允许新车辆加入，所以流入等于流出，这便是一个典型的网络流。
电网电流、供水水流、金融现金流本质也类似
我们现在来给出抽象定义：
设有向连通图$N=<V,E>$，$n=|V|,m=|E|$，每条边$<i,j>$的容量为非负实数$c(i,j)$，$N$有两个特殊顶点$s,t$，$s$称作发点或源，$t$称作收点或汇，其余顶点为中间点
此时我们就称$N$为容量网络，记作$N=<V,E,c,s,t>$
记$f:E \rightarrow R^{\ast}$，其中$R^{\ast}$为非负实数集，若$f$满足：
- $\forall <i,j> \in E,f(i,j) \le c(i,j)$ 容量限制
- $\forall i \in V-[s,t],\Sigma_{<j,i>\in E}f(j,i)=\Sigma_{<i,j>\in E}f(i,j)$ 平衡条件，流入等于流出
我们就称$f$为$N$上的一个可行流，记$s$点净流出量为$f$流量，记作$v(f)$
$v(f)=\Sigma_{<s,j>\in E}f(s,j)-\Sigma_{<j,s>\in E}f(j,s)$
显然流量也等于收点的净流入量，即
$v(f)=\Sigma_{<j,t>\in E}f(j,t)-\Sigma_{<t,j>\in E}f(t,j)$
既然有了许多种可行流，我们就将流量最大的称为最大流
于是给定容量网络的最大流问题可以转化为线性规划问题：
$max\ v(f)$
$s.t\ f(i,j) \le c(i,j), \ <i,j> \in E$ 容量限制
$\Sigma_{<j,i>\in E}f(j,i)-\Sigma_{<i,j>\in E}f(i,j)=0,\ i \in V-[s,t]$ 平衡条件
$v(f)-\Sigma_{<s,j>\in E}f(s,j)+\Sigma_{<j,s>\in E}f(j,s)=0$ 流量定义
$f(i,j) \ge 0, \ <i,j> \in E$
$v(f)\ge 0$
下面是一个很容易理解的例子
由于最大流问题十分重要，线性规划效率不够高，研究人员开发了许多更有效的算法，下面我们通过了解最大流的性质探究之
定义：容量网络$N=<V,E,c,s,t>$，$A \subset V,s \in A,t \in \bar{A}$
称$(A,\bar{A})=[<i,j>|<i,j> \in E,i \in A,j \in \bar{A}]$为$A$的割集
$c(A,\bar{A})=\Sigma_{<i,j>\in (A,\bar{A})}c(i,j)$为割集$(A,\bar{A})$的容量
容量最小的割集就被称为最小割集
从直觉来看，$N$的任何可行流都需要通过割集中的边从$A$流向$\bar{A}$，因此任何可行流容量不会超过割集容量
证明如下，由于公式过多这里就直接插图片了
因此我们有：
$\forall N$上可行流$f$，$v(f) \le c(A,\bar{A})$
如果刚好取等，则刚好就是最大流和最小割集
FF算法
下面我们介绍Ford-Fulkerson算法
首先定义，在$N$中：
流量等于容量的边为饱和边，流量小于容量的边为非饱和边
流量等于0的为零流边，大于0的为非零流边
不考虑边的方向，$N$中从顶点$i$到$j$的一条边不重复的路径称为i-j链，方向从$i$到$j$
在链中，与链方向一致的边为前向边，不一致为后向边
如果所有前向边非饱和，后向边非零流，则称这条链为i-j增广链
那么我们大费周章弄出这个增广链，有何作用？
假设找到了$P$为增广链，令修改量$\delta$为 所有前向边容量与流量之差 和 所有后向边流量的 最小值，显然$\delta>0$
于是我们就可以修改$f$的值，令$f’(i,j)=$
- $f(i,j)+ \delta, \ <i,j>$为前向边
- $f(i,j)- \delta, \ <i,j>$为后向边
- $f(i,j)$,其余情况
不难证明此时的$f’$也是可行流，且$v(f’)=v(f)+\delta$
所以若$f$已经是最大流，就不存在 s-t 增广链
反过来也成立，我们来证明一下：
当然上面也证明出了$(A,\bar{A})$为最小割集，于是有下述定理
最大流最小割定理：容量网络最大流的流量等于最小割集容量
接下来我们看FF算法，它的步骤通常如下：
从给定的初始可行流(通常取零流)开始，寻找一条关于当前可行流的 s-t 增广链P，然后按照上面的方法修改其流量，重复上述过程直至不存在 s-t 增广链
具体寻找 s-t 增广链时，从s开始搜索，逐个给顶点标号，直至t得到标号为止。如果顶点j得到标号，就说明已经找到s-j增广链，标号为$(l_j,\delta_j)$
其中$\delta_j$类似前面的定义，为直到j为止链上 所有前向边容量与流量之差 和 所有后向边流量的 最小值
$l_j=i$或$-i$，$=i$表示链为$i$到$j$且$<i,j>$为前向边，$=-i$表示链为$i$到$j$且$<j,i>$为后向边
顶点分为三类：已标号已检查，已标号未检查，未标号
开始给$s$标号$(\Delta,+ \infty)$，$\Delta$表示发点，此时$s$是已标号未检查，其余都是未标号
每一步取一个已标号未检查的顶点$i$，对于所有顶点$j$
- 若$<i,j> \in E$且$f(i,j)<c(i,j)$，前向边情况，则$j$标号$(+i,\delta_j)$，其中$\delta_j=min(\delta_i,c(i,j)-f(i,j))$
- 若$<j,i> \in E$且$f(j,i)>0$，后向边情况，则$j$标号$(-i,\delta_j)$，其中$\delta_j=min(\delta_i,f(j,i))$
具体伪代码如下：
时间复杂度：假设所有容量和每一次的$\delta$均为正整数，记$C=\Sigma_{<s,j>\in E}c(s,j)$，显然最大流量$v^{\ast} \le C$
由于$\delta$为正整数，最多有$C$个阶段，每个阶段标号和修改流量复杂度$O(m)$
故总时间复杂度为$O(mC)$
Dinic算法
FF算法没有给出具体标号过程的细节顺序，这就给我们留下了很大的改进空间
Dinic算法给出了两点改进：
- 每次求最短的(边数最少)的 s-t 增广链
- 一次标号修改尽可能多条 s-t 增广链上的流量
还是容量网络$N=<V,E,c,s,t>$，$f$为$N$可行流，我们定义$f$的辅助网络$N(f)=<V,E(f),ac,s,t>$，其中：
$E^{+}(f)=[<i,j>|<i,j> \in E,f(i,j)<c(i,j)]$
$E^{-}(f)=[<j,i>|<i,j> \in E,f(i,j)>0]$
$E(f)=E^{+}(f)\cap E^{-}(f)$
$ac(i,j)=$
- $c(i,j)-f(i,j),\ <i,j>\in E^{+}(f)$
- $f(j,i),\ <i,j>\in E^{-}(f)$
ac为辅助容量，可以看出$N(f)$也是容量网络
由于我们约定了$N$中任意两点最多只有一条边，因此$N(f)$中没有平行边
不难看出，$N$中关于$f$的 s-t 增广链即为$N(f)$中$s$到$t$的有向路径
引理：$N$最大流量为$v^{\ast}$，则$N(f)$最大流量为$v^{\ast}-v(f)$
接下来我们从$s$开始用BFS，按照与$s$的距离$d(i)$，把顶点划分为不相交的层
$d(s)=0$，$s$为第0层，从$s$到$t$的最短路只可能从$s$到1层、2层……以此类推直到$t$
最短路径之外不可能出现从高层到低层的边，同一层顶点之间的边，除$t$之外层数$\ge d(t)$的顶点
于是我们将这些边和顶点全部删除之后的网络称为分层辅助网络$AN(f)=<V(f),AE(f),ac,s,t>$
$V(f)=\cup_{k=0}^{d} V_k(f)$
$AE(f)=\cup_{k=0}^{d-1}[<i,j>|<i,j> \in E(f) \land i \in V_k(f),j \in V_{k+1}(f)]$
$V_k(f)=[i \in V|d(i)=k], \ 0\le k \le d-1$
$V_d(f)=t$
下面是一个例子：
为了一睹Dinic算法的真面目，我们还需要最后的几个定义：
- 前向增广链：关于$f$的没有后向边的增广链
- 极大流：不存在前向增广链的可行流
最大流一定是极大流，反之不一定 - 中间点$i$流通量$th(i)$：以 $i$ 为终点的边的容量之和与以 $i$ 为始点的边的容量之和中较小者
现在万事俱备，我们终于可以介绍Dinic算法了！
关键就是要求$AN(f)$的极大流
- 在 $AN(f)$ 中找尽可能多的从 $s$ 到 $t$ 的最短路径并给出这些路径上的容量
- 删去流通量为0的顶点及关联的边. 找到流通量最小的顶点$k$, 从$k$开始向后和向前安排流量 $th(k)$, 直到 $t$ 和 $s$ 为止. 修改相关边的容量
- 得到$AN(f)$的极大流 $g$，令$f’=f+g$，重复进行, 直到 $s$ 和 $t$ 不连通为止，此时的$f$即为最大流
伪代码如下：
一些结论：
- 每个阶段结束时，$g$为$AN(f)$极大流
- 每个阶段$AN(f+g)$的 s-t 距离大于前一个阶段$AN(f)$的 s-t 距离
- 最后得到的$f$为最大流
这是由于算法终止时$AN(f)$中不存在 s-t 的路径，因此$N(f)$中也没有，则$N(f)$最大流量为$v^{\ast}-v(f)$为零流，故$v(f)=v^{\ast}$，$f$为最大流 - 算法在$O(n^3)$步内终止
阶段数量$\le n$
每阶段工作量：- 构造$AN(f)$：$O(m)$
- 计算流通量：$O(m)$
- 找最小流通量顶点：最多$n$次，$O(n^2)$
- 边操作：$O(m)+O(n^2)$
- 如果对于简单容量网络(边容量为1，中间点入度为1或出度为1)，时间可以优化到$O(n^{0.5}m)$
最小费用流
问题定义
在原有的容量网络$N=<V,E,c,s,t>$中添加单位费用$w:E \rightarrow R^{\ast}$
就变成了容量-费用网络，记作$N=<V,E,c,w,s,t>$
记$f$为$N$上一个可行流，称$w(f)=\Sigma_{<i,j>\in E}w(i,j)f(i,j)$为$f$的费用
所有流量为$v_0$的可行流中，费用最小的称作流量$v_0$的最小费用流
具体算法
和最大流问题类似地，定义辅助网络$N(f)=<V,E(f),ac,aw,s,t>$
其中辅助费用$aw(i,j)=$
- $w(i,j), \ <i,j> \in E^{+}(f)$
- $-w(j,i), \ <i,j> \in E^{-}(f)$
若$g$为$N(f)$可行流，则有$w(f+g)=w(f)+aw(g)$
下面对$N$中任意 边不重复 的回路$C$，定义$h^{C}$为$C$上的圈流：
- $\forall <i,j> \in E( C ),h^{C}(i,j)=\delta$
- $\forall <i,j> \in E-E( C ),h^{C}(i,j)=0$
其中$\delta>0$，为$h^{C}$的环流量
圈流有如下性质：
- $h^{C}$为可行流， 且$v(h^{C})=0$，$w(h^{C})=\delta \cdot w( C )$
- $v(f+h^{C})=v(f)$，$w(f+h^{C})=w(f)+\delta \cdot aw( C )$
下面是一个例子：
一定要认真看一下这个图，这将是前面所有抽象概念的集大成之作！
在图1中每条边标注的第一个数字(黑色)表示容量，每条边标注的第二个数字(蓝色)表示费用，故流量$v_0=3+5=8$，费用$w(f)=5 \times 3+5\times3+3\times3+3\times1=42$
图2中看上去就有点乱了，让我们回顾一下$N(f)$
例如由s到2，$E^{+}(f)$容量为$5-3=2$，方向依旧正向，费用不变
$E^{-}(f)$容量为$3$，方向变为反向，费用变为$-3$
然后图中橙色为回路$C(1 \rightarrow 2 \rightarrow t \rightarrow 1)$
由于都是正向边，$w( C )=aw( C )=1+1-3=-1$
$\delta=3$(回路上所有边残余容量的最小值)
故$w(h^{C})=aw(h^{C})=\delta \cdot w( C )=-3$
图3就是算法中的重要操作：更新流$f_1=f+h^{C}$，得到费用更低的可行流
对于$C$，回路正向边流量$+\delta$，回路反向边流量$-\delta$
例如$1-2$容量$+3$，$2-t$容量$+3$，$1-t$容量$-3$
更新之后的费用$w(f_1)=5\times3+3\times3+3\times1+2\times3+6\times1=39$，费用有效减少了
于是我们得到了一个求最小费用流的有效算法：
- 首先求一个流量$v_0$可行流$f$
- 如果$N(f)$中存在回路$C$，$aw (C )<0$，那么就可以对$f$加上$h^{C}$来更新
- 重复进行直至$N(f)$中不存在$aw( C )<0$的回路$C$，此时$f$即为最小费用流
如何求负回路
对于回路$C$来说，$aw( C )$本质上就是$C$每边的费用加和
所以要找$aw( C )<0$的回路$C$，就是在有向带权图中寻找负回路
引理：图中任意两点间要么有最短路径，要么不存在路径 $\iff$ 图中没有负回路
由此，我们可以将负回路的存在问题转化为多源最短路径问题
于是梦回数算！下面就是Floyd算法回归的时刻了
记$d^{k}(i,j)$为$i$到$j$经过号码不大于$k$的最短路径长度
则类似dp，我们有递推式：
$d^{(0)}(i,j)=w(i,j),d^{(0)}(i,i)=0$
$d^{(k)}(i,j)=min(d^{(k-1)}(i,j),d^{(k-1)}(i,k)+d^{(k-1)}(k,j))$
若存在$i$使得$d^{(n)}(i,i)<0$，则有负回路
为了记录路径，我们记$h^{(k)}(i,j)$为$i$到$j$经过号码不大于$k$的最短路径中$i$的下一个顶点
则有$h^{(0)}(i,j)=$
- $j,\ <i,j> \in E$
- $0,\ else$
$h^{(k)}(i,j)=$
- $h^{(k-1)}(i,j), \ d^{(k-1)}(i,j)\le d^{(k-1)}(i,k)+d^{(k-1)}(k,j)$
- $h^{(k-1)}(i,k), \ else$
当然，最短路径也有别的方法，比如从零流开始，每次用floyd(若存在负回路)或者ford算法找费用最小的 s-t增广链，增广直至流量达到$v_0$，这里就不再赘述了
网络流的应用
带需求的流通
给定流通图$N=<V,E,c,s,t>$
非常烦人的是$\forall v \in V,\exists d_v$为需求
- 收点：$d_v >0$，表示$v$对流有$d_v$的需求
- 发点：$d_v <0$，表示$v$对流有$-d_v$的供给
- 结点：既不是发点也不是收点，$d_v=0$
所有容量和需求均为整数
问：是否存在可行流通，即存在函数$f:E \rightarrow R^{\ast}$，满足
- 容量条件：$\forall e \in E, 0 \le f(e) \le c_e$
- 需求条件：$\forall v \in V,f^{in}(v)-f^{out}(v)=d_v$
从经济学的角度来说()，由于没有外部因素，供需是平衡的
因此有$\Sigma_{v:d_v >0}d_v=\Sigma_{v:d_v <0}-d_v$，我们记这个和为$D$
于是可以用最大流进行建模，记所有发点的集合$S$，收点集合$T$
我们增加超结点$s^{\ast}$和$t^{\ast}$，构建单发点单收点的容量网络$G’$
$\forall v \in S$，加边$e=<s^{\ast},v>,c_e=-d_v$
$\forall v \in T$，加边$e=<v,t^{\ast}>,c_e=d_v$
具体算法：
- 将$G$转换为对应$G’$
- 对$G’$用最大流算法找到$s^{\ast}$-$t^{\ast}$最大流$f$
- 若$v(f)=D$，则$G$存在需求$d_v$的可行流通，否则不存在
扩展：带下界的可行流通，$\forall e \in E,l_e \le f(e) \le c_e$，需求条件不变
运输问题
有$m$个产地$A_1,A_2,…,A_m$，$n$个销地$B_1,B_2,…,B_n$
$A_i$产量$a_i$，$B_j$销量$b_j$，从$A_i$到$B_j$单位运费$w_{ij}$
我们假设产销平衡，$\Sigma_{i=1}^{m}a_i=\Sigma_{j=1}^{n}b_j$
求使总运费最少的运输方案
我们设运输方案为$x$，即在$A_i,B_j$之间运输$x_{ij}$的货物
则有$x_{ij} \ge 0$
$\Sigma_{j=1}^{n}x_{ij}=a_i$
$\Sigma_{i=1}^{m}x_{ij}=b_j$
总费用$w(x)=\Sigma_{i=1}^{m}\Sigma_{j=1}^{n}w_{ij}x_{ij}$
我们要求使得$w(x)$最小的方案$x$
建模时，依旧是添加$s,t$，组成容量费用网络$N=<V,E,c,w,s,t>$
如图所示
其中：
- $s-A_i$的边，容量为$a_i$，费用为$0$
- $B_i-t$的边，容量为$b_i$，费用为$0$
- $A_i-B_i$的边，容量为$+ \infty$，费用为$w_{ij}$
于是总运费最少的运输方案就转化为求流量$v_0=\Sigma_{i=1}^{m}a_i$的最小费用流
图像分割
我们需要将图像的前景和背景分离，这就得对每个像素，标记其是属于前景$A$还是背景$B$
设$V$为像素集合，用$E$表示所有相邻像素对的集合，形成无向图$G=<V,E>$
对像素$i$，记它属于前景的可能性$a_i$，属于背景的可能性$b_i$
显然如果$a_i>b_i$，就将其标记为前景，否则就是背景
记集合$A$为标记为前景的像素，$B$为背景像素
如果像素$i$的“邻居”都被标记为背景，我们就倾向于也将其标为背景，这样可以使标记更光滑
因此我们对于每组邻居$(i,j)$，定义惩罚$p_{ij}$，惩罚他们标记不同
则图像分割问题就变成了最大化权值$q(A,B)=$
$\Sigma_{i \in A}a_i+\Sigma_{j \in B}b_j-\Sigma_{(i,j) \in E且标记不同} \ p_{ij}$
我们记$Q=\Sigma_i (a_i+b_i)$，则$q(A,B)=Q-q’(A,B)$
$q’(A,B)=\Sigma_{i \in A}b_i+\Sigma_{j \in B}a_j-\Sigma_{(i,j) \in E且标记不同} \ p_{ij}$
由于$Q$为定值，最大化$q(A,B)$等价于最小化$q’(A,B)$
为什么要如此转化呢？下面我们建模
构造容量网络$G’$，源点$s$(前景)，汇点$t$(背景)
对于每个像素$v$，连边$(s,v),(t,v)$，容量分别为$a_v,b_v$
对每条无向边$(u,v)$，将其转化为两条有向边$<u,v>,<v,u>$，容量均为$p_{uv}$
记$A’=A \cup s$，$B’=B \cup t$，由此我们可以计算割$(A’,B’)$的容量
于是最大化$q(A,B)$等价于求最小割集$(A’,B’)$
算法的时间复杂度为$O(n^3)$