文档网络流算法.docx
《文档网络流算法.docx》由会员分享，可在线阅读，更多相关《文档网络流算法.docx（49页珍藏版）》请在冰点文库上搜索。
文档网络流算法
第三节网络流算法
一、网络流的基本概念
先来看一个实例。
现在想将一些物资从S运抵T，必须经过一些中转站。
连接中转站的是公路，每条公路都有最大运载量。
如下图：
每条弧代表一条公路，弧上的数表示该公路的最大运载量。
最多能将多少货物从S运抵T？
这是一个典型的网络流模型。
为了解答此题，我们先了解网络流的有关定义和概念。
若有向图G=（V,E）满足下列条件：
1、有且仅有一个顶点S，它的入度为零，即d-（S）=0，这个顶点S便称为源点，或称为发点。
2、有且仅有一个顶点T，它的出度为零，即d+（T）=0，这个顶点T便称为汇点，或称为收点。
3、每一条弧都有非负数，叫做该边的容量。
边（vi,vj）的容量用cij表示。
则称之为网络流图，记为G=（V,E,C）
譬如图5-1就是一个网络流图。
1．可行流
对于网络流图G，每一条弧（i,j）都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
1、每一条弧（i,j）有fij≤cij。
2、除源点S和汇点T以外的所有的点vi，恒有：
该等式说明中间点vi的流量守恒，输入与输出量相等。
3、对于源点S和汇点T有：
这里V（f）表示该可行流f的流量。
例如对图5-1而言，它的一个可行流如下：
流量V（f）=5。
2．可改进路
给定一个可行流f={fij}。
若fij=cij，称为饱和弧；否则称为非饱和弧。
若fij=0，称为零流弧；否则称为非零流弧。
定义一条道路P，起点是S、终点是T。
把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。
譬如在图5-1中，P=（S,V1,V2,V3,V4,T），那么
P+={,,,}
P-={}
给定一个可行流f，P是从S到T的一条道路，如果满足：
那么就称P是f的一条可改进路。
（有些书上又称：
可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。
具体方法下一节会重点介绍，此不赘述。
3．割切
要解决网络最大流问题，必须先学习割切的概念和有关知识。
G=（V,E,C）是已知的网络流图，设U是V的一个子集，W=V\U，满足S
U，T
W。
即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。
对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。
把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：
例如图5-1中，令U={S,V1}，则W={V2,V3,V4,T}，那么
C（U,W）=+++=8+4+4+1=17
定理：
对于已知的网络流图，设任意一可行流为f，任意一割切为（U,W），必有：
V（f）≤C（U,W）。
通俗简明的讲：
“最大流小于等于最小割”。
这是“流理论”里最基础最重要的定理。
整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。
下面我们给出证明。
证明对任意一个中间点（即非S、也非T的点）vi，恒有：
（1）
当vi=S时有
（2）
从
（1）、
（2）对i∈U求和得
因为：
V=U∪W，所以
又因：
即
故有：
所以
即V（f）≤C（U,W）
命题得证。
网络流、可改进路、割切都是基础的概念，应该扎实掌握。
它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。
二、求最大流
何谓最大流？
首先它必须是一个可行流；其次，它的流量必须达到最大。
这样的流就称为最大流。
譬如对图5-1而言，它的最大流如下：
下面探讨如何求得最大流。
在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。
下面我们就具体看一看是什么“规则”。
对可改进路P上的弧，分为两种情况讨论：
第一种情况：
∈P+，可以令fij增加一个常数delta。
必须满足fij+delta≤cij，即delta≤cij–fij。
第二种情况：
∈P-，可以令fij减少一个常数delta。
必须满足fij-delta≥0，即delta≤fij
根据以上分析可以得出delta的计算公式：
因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，所以delta>0。
容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”（即输入量等于输出量），又可以使得总的流量有所增加（因为delta>0）。
因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。
我们要求的是最大流，现在的问题是：
倘若在f中找不到可改进路，是不是f就一定是最大流呢？
答案是肯定的。
下面我们给出证明。
定理1可行流f是最大流的充分必要条件是：
f中不存在可改进路。
证明：
首先证明必要性：
已知最大流f，求证f中不存在可改进路。
若最大流f中存在可改进路P，那么可以根据一定规则（详见上文）修改P中弧的流量。
可以将f的流量放大，这与f是最大流矛盾。
故必要性得证。
再证明充分性：
已知流f，并且f中不存在可改进路，求证f是最大流。
我们定义顶点集合U,W如下：
（a）S∈U，
（b）若x∈U，且fxy若x∈U，且fyx>0，则y∈U。
（这实际上就是可改进路的构造规则）
（c）W=V\U。
由于f中不存在可改进路，所以T∈W；又S∈U，所以U、W是一个割切（U,W）。
按照U的定义，若x∈U，y∈W，则fxy=cxy。
若x∈W，y∈U，则fxy=0。
所以，
又因v（f）≤C（U,W）
所以f是最大流。
得证。
根据充分性证明中的有关结论，我们可以得到另外一条重要定理：
最大流最小割定理：
最大流等于最小割，即maxV（f）=minC（U,W）。
至此，我们可以轻松设计出求最大流的算法：
step1.令所有弧的流量为0，从而构造一个流量为0的可行流f（称作零流）。
step2.若f中找不到可改进路则转step5；否则找到任意一条可改进路P。
step3.根据P求delta。
step4.以delta为改进量，更新可行流f。
转step2。
step5.算法结束。
此时的f即为最大流。
下面看一个实例。
求图5-4所示网络流图的最大流。
图中弧上的数字是该弧的容量。
第一步，令所有弧的流量为0。
找到一条可改进路P=（S,V1,V2,T），delta=min{4-0,2-0,4-0}=2。
找到一条可改进路P=（S,V1,T），delta=min{4-2,4-0}=2
这时又找到一条可改进路P=（S,V2,V1,T），P+={,}，P-={}。
此时，
delta=min{Cs2–FS2，C1t–F1t，F12}=min{4–0,4–2,2}=2
新的流如下：
（反向弧F12被减少了2）
最后找到一条可改进路P={S,V2,T}，delta=2。
对此流再也找不到可改进路了。
所以它就是图2所示网络流图的最大流。
再回到求网络最大流的算法中来。
算法的关键步骤是step2，即：
判断是否存在可改进路，若存在又如何求。
可以考虑用广度优先搜索。
设置标志数组，记录顶点是不是被访问过；使用队列来存储已经访问过的顶点；另用一个一维数组，记录每个顶点是由哪个顶点扩展而来（即记录父亲节点）。
首先S入队列。
然后每次取队首顶点v，分析所有与v相邻的未访问顶点u：
1、存在弧（正向弧），且u未访问。
若fvu2、存在弧（反向弧），且u未访问。
若fuv>0（非零流弧），那么u入队列，给u打上“已访问”的标志，记u的父亲节点为-v。
（以示和正向弧的区别）。
扩展完成后，若T还没有被访问就必然不存在可改进路；否则就从T出发，根据记录好的每个顶点的父亲节点信息，顺藤摸瓜，找出可改进路（同时还可以计算出delta）。
这只是算法的初步勾勒，具体细节的优化余地极大，留给读者思考。
注：
有些书上是介绍的用“标号法”求可改进路。
“标号法”实质上就是广搜，只是细节的实现上略有偏差。
【程序】
{程序中以1为源点，n为汇点}
programmax_flow;
const
fin='maxflow.in';
fout='maxflow.out';
maxn=100;
type
tline=array[0..maxn]ofinteger;
tmap=array[1..maxn]oftline;{网络流图的邻接矩阵}
var
n:
integer;
limit,flow:
tmap;{上界和流量}
proceduregetinfo;{读入数据}
var
i,j,c:
integer;
begin
assign（input,fin）;reset（input）;
readln（n）;
whilenotseekeofdobegin
readln（i,j,c）;
limit[i,j]:
=c;
end;
close（input）;
end;
proceduremaxflow;{最大流}
var
i,j,delta,x:
integer;
last:
tline;{可改进路中的前趋}
check:
array[0..maxn]ofboolean;{是否已经检查过}
begin
repeat
fillchar（last,sizeof（last）,0）;
fillchar（check,sizeof（check）,false）;
last[1]:
=maxint;
repeat
i:
=0;repeatinc（i）until（i>n）or（last[i]<>0）andnotcheck[i];
{找到一个已检查而未标号的点}
ifi>nthenbreak;
forj:
=1tondoiflast[j]=0then
ifflow[i,j]=ielse{正向弧}
ifflow[j,i]>0thenlast[j]:
=-i;{反向弧}
check[i]:
=true;
untillast[n]<>0;
iflast[n]=0thenbreak;
delta:
=maxint;
i:
=n;
repeat
j:
=i;i:
=abs（last[j]）;
iflast[j]>0thenx:
=limit[i,j]-flow[i,j]elsex:
=flow[j,i];
ifx=x;
untili=1;{求改进量}
i:
=n;
repeat
j:
=i;i:
=abs（last[j]）;
iflast[j]>0theninc（flow[i,j],delta）elsedec（flow[j,i],delta）;
untili=1;{放大网络流}
untilfalse;
end;
procedureprint;{输出}
var
i,j,sum:
integer;
begin
sum:
=0;
assign（output,fout）;rewrite（output）;
fori:
=1tondo
forj:
=1tondoifflow[i,j]>0thenbegin
ifi=1theninc（sum,flow[i,j]）;
writeln（i,'-->',j,'',flow[i,j]）;
end;
writeln（'maxflow=',sum）;
close（output）;
end;
begin
getinfo;{输入}
maxflow;{加工}
print;{输出}
end.
三、最小费用最大流
1．问题的模型
流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。
然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。
图5-8是一个最简单的例子：
弧上标的两个数字第一个是容量，第二个是费用。
这里的费用是单位流量的花费，譬如fs1=4，所需花费为3*4=12。
容易看出，此图的最大流（流量是8）为：
fs1=f1t=5,fs2=f2t=3。
所以它的费用是：
3*5+4*5+7*3+2*3=62。
一般的，设有带费用的网络流图G=（V,E,C,W），每条弧对应两个非负整数Cij、Wij，表示该弧的容量和费用。
若流f满足：
（a）流量V（f）最大。
（b）满足a的前提下，流的费用Cost（f）=
最小。
就称f是网络流图G的最小费用最大流。
2．算法设计
我们模仿求最大流的算法，找可改进路来求最小费用最大流。
设P是流f的可改进路，定义
为P的费用（为什么如此定义？
）。
如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。
求最小费用最大流的基本思想是贪心法。
即：
对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。
这样的得到的最大流必然是费用最小的。
算法可描述为：
step1.令f为零流。
step2.若无可改进路，转step5；否则找到最小费用可改进路，设为P。
step3.根据P求delta（改进量）。
step4.放大f。
转step2。
step5.算法结束。
此时的f即最小费用最大流。
至于算法的正确性，可以从理论上证明。
读者可自己思考或查阅有关运筹学资料。
2．最小费用可改进路的求解
求“最小费用可改进路”是求最小费用最大流算法的关键之所在，下面我们探讨求解的方法。
设带费用的网络流图G=（V,E,C,W），它的一个可行流是f。
我们构造带权有向图B=（V’,E’），其中：
1、V’=V。
2、若∈E，fij∈E’，权为Wij。
若∈E，fij>0，那么∈E’，权为-Wij。
显然，B中从S到T的每一条道路都对应关于f的一条可改进路；反之，关于f的每条可改进路也能对应B中从S到T的一条路径。
即两者存在一一映射的逻辑关系。
故若B中不存在从S到T的路径，则f必然没有可改进路；不然，B中从S到T的最短路径即为f的最小费用可改进路。
现在的问题变成：
给定带权有向图B=（V’,E’），求从S到T的一条最短路径。
考虑到图中存在权值为负数的弧，不能采用Dijkstra算法；Floyd算法的效率又不尽如人意——所以，这里采用一种折衷的算法：
迭代法。
设Short[i]表示从S到i顶点的最短路径长度；从S到顶点i的最短路径中，顶点i的前趋记为Last[i]。
那么迭代算法描述如下：
（为了便于描述，令n=|V’|，S的编号为0，T的编号为n+1）
step1.令Short[i]ß+∞（1≤i≤n+1），Short[0]ß0。
step2.遍历每一条弧。
若Short[i]+，同时Last[j]ßi。
倘不存在任何一条弧满足此条件则转step4。
step3.转step2.
step4.算法结束。
若Short[n+1]=+∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。
一次迭代算法的时间复杂度为O（kn2），其中k是一个不大于n的变量。
在费用流的求解过程中，k大部分情况下都远小于n。
【程序】
{程序中以1为源点，n为汇点}
programcost_flow;
const
fin='costflow.in';
fout='costflow.out';
maxn=100;
type
tline=array[0..maxn]ofinteger;
tmap=array[1..maxn]oftline;
var
n:
integer;
limit,cost,flow:
tmap;{上界、费用、流量}
proceduregetinfo;{读入数据}
var
i,j,c,w:
integer;
begin
assign（input,fin）;reset（input）;
readln（n）;
whilenotseekeofdobegin
readln（i,j,c,w）;
limit[i,j]:
=c;cost[i,j]:
=w;
end;
close（input）;
end;
procedureprint;{输出}
var
i,j,sum,acost:
integer;
begin
assign（output,fout）;rewrite（output）;
sum:
=0;acost:
=0;
fori:
=1tondo
forj:
=1tondoifflow[i,j]>0thenbegin
ifi=1theninc（sum,flow[i,j]）;
inc（acost,flow[i,j]*cost[i,j]）;
writeln（i,'-->',j,'',flow[i,j]）;
end;
writeln（'maxflow=',sum）;
writeln（'mincost=',acost）;
close（output）;
end;
procedurecostflow;{求最小费用最大流}
var
i,j,x,delta:
integer;
best,last:
tline;{best：
最短路长度；last：
可改进路中的前趋顶点}
more:
boolean;
begin
repeat
fillword（best,sizeof（best）shr1,maxint）;
fillchar（last,sizeof（last）,0）;
last[1]:
=maxint;best[1]:
=0;{赋初值}
repeat
more:
=false;
fori:
=1tondoifbest[i]<>maxintthen
forj:
=1tondobegin
if（flow[i,j]best[j]:
=best[i]+cost[i,j];
last[j]:
=i;
more:
=true;
end;
if（flow[j,i]>0）and（best[i]-cost[j,i]best[j]:
=best[i]-cost[j,i];
last[j]:
=-i;
more:
=true;
end;
end;
untilnotmore;{找最优可改进路}
ifbest[n]=maxintthenbreak;
delta:
=maxint;
i:
=n;
repeat
j:
=i;i:
=abs（last[j]）;
iflast[j]>0thenx:
=limit[i,j]-flow[i,j]elsex:
=flow[j,i];
ifx=x;
untili=1;{求改进量}
i:
=n;
repeat
j:
=i;i:
=abs（last[j]）;
iflast[j]>0theninc（flow[i,j],delta）elsedec（flow[j,i],delta）;
untili=1;
untilfalse;{根据改进量放大流}
end;
begin
getinfo;{输入}
costflow;{计算}
print;{输出}
end.
3．思维发散与探索
1）可改进路费用：
“递增！
递增？
”
设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢？
2）迭代法：
“小心死循环！
嘿嘿……”
迭代法会出现死循环吗？
也就是说，构造的带权有向图B中会存在负回路吗？
3）费用：
“你在乎我是负数吗？
”
网络流图中的费用可以小于零吗？
4）容量：
“我管的可不仅是弧。
”
网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制：
即通过此顶点的流量的上限；任务仍然是求从S到T的最小费用最大流。
你能解决吗？
四、有上下界的最大流
上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧加上一个下界限制Aij（即必须满足Aij≤fij）。
例如图5-9：
弧上数字对第一个是上界，第二个是下界。
若是撇开下界不看，此图的最大流如图5-10（a）所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具体方案见图5-10（b）。
那么有上下界的网络最大流怎么求呢？
一种自然的想法是去掉下界，将其转化为只含上界的网络流图。
这种美好的愿望是可以实现的。
具体方法如下：
设原网络流图为G=（V,E,C,A），构造不含下界的网络流图G’=（V’,E’,C’）：
1、V’=V∪{S’,T’}
2、对每个顶点x，令
，若h-（x）≠0，就添加一条弧，其上界为h-（x）。
3、对每个顶点x，令
，若h+（x）≠0，就添加一条弧，其上界为h+（x）。
4、对于任
升级会员 