《网络流讲义732.pdf》由会员分享，可在线阅读，更多相关《网络流讲义732.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、网络流算法及其应用 5.1 基本概念 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50 年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立个网络流模型，然后用最大流算法高效地解决问题。1.问题描述 如图 5-1 所示是联结某产品地 v1 和销售地 v4 的交通网，每一弧(vi,vj)代表从
2、vi 到vj 的运输线，产品经这条弧由 vi 输送到 vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从 v1 到 v4。现在要求制定一个运输方案使从 v1 到 v4 的产品数量最多。图 5-1 图 5-2 2.网络与网络流 给一个有向图 N=(V，E)，在 V 中指定一点，称为源点(记为 vs，和另一点，称为汇点(记为 vt)，其余的点叫中间点，对于 E 中每条弧(vi，vj)都对应一个正整数 c(vi，vj)O(或简写成 cij)，称为f 的容量，则赋权有向图 N=(V，E，c，vs，vt)称为一个网络。如图 5-1 所给出的一个赋权有向图 N 就是一个网络，指定 v1 是源点，
3、v4 为汇点，弧旁的数字为 cij。所谓网络上的流，是指定义在弧集合 E 上一个函数 f=f(vi，vj)，并称 f(vi，vj)为弧(vi，vj)上的流量(下面简记为 fij)。如图 5-2 所示的网络 N，弧上两个数，第一个数表示容量 cij，第二个数表示流量 fij。3.可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为 0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：(1)容量约束：0fijcij，(vi,vj)E，(2)守恒条件 对于中间点：流入量=流出量
4、；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流 f，称为网络 N 上的可行流，并将源点 s 的净流量称为流 f 的流值 v(f)。网络 N 中流值最大的流 f*称为 N 的最大流。4.可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。设 f 是一个可行流，P 是从源点 s 到汇点 t 的一条路，若 p 满足下列条件：(1)在 p 上的所有前向弧(vivj)都是非饱和弧，即 0fijcij (2)在 p 上的所有后向弧(vivj)都是非零弧，即 0fijcij 则称 p 为(关于可行流 f 的)一条可增广路径。5.最大流定理
5、 当且仅当不存在关于 f*的增广路径，可行流 f*为最大流。5.2 最大流算法 算法思想:最大流问题实际上是求一可行流fij，使得 v(f 达到最大。若给了一个可行流 f，只要判断 N 中有无关于 f 的增广路径，如果有增广路径，改进 f，得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。1.寻求最大流的标号法(Ford,Fulkerson)从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于 f的可增广路径为止。(1)标号过程 在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个 部分：第一标号
6、表明它的标号从哪一点得到的，以便从 vt 开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。标号开始时，给 vs 标上(s，0)，这时 vs 是标号但末检查的点，其余都是未标号的点，记为(0，0)。取一个标号而未检查的点 vi，对于一切未标号的点 vj：A对于弧(vi，vj)，若 fij0，则给 vj 标号(-vi，0)，这时，vj 点成为标号而未检查的点。于是 vi 成为标号且已检查的点，将它的第二个标号记为 1。重复上述步骤，一旦 vt 被标上号，表明得到一条从 vi 到 vt 的增广路径 p，转入调整过程。若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的
7、可行流就是最大流。(2)调整过程 从 vt 点开始，通过每个点的第一个标号，反向追踪，可找出增广路径 P。例如设 vt 的第一标号为 vk(或-vk)，则弧(vk，vt)(或 相应地(vt，vk)是 p 上弧。接下来检查 vk 的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi)。再检查 vi 的第一 标号，依此类推，直到 vs 为止。这时整个增广路径就找到了。在上述找增广路径的同时计算 Q：Q=minmin(cij-fij)，minf*ij 对流 f 进行如下的修改：fij=fij+Q (vi，vj)P 的前向弧的集合 fij=fij-Q (vi，vj)P 的后向弧
8、的集合 fij=f*ij (vi，vj)不属于 P 的集合 接着，清除所有标号，对新的可行流 f，重新进入标号过程。例 1:下图表示一个公路网,V1 是某原材料产地,V6 表示港口码头,每段路的通过能力(容量)如图上的各边上的数据,找一运输方案,使运输到码头的原材料最多?程序如下:Program Max_Stream;Const Maxn=20;type nettype=record C,F:integer;end;nodetype=record L,P:integer;end;var Lt:array0.maxn of nodetype;G:Array0.Maxn,0.Maxn of Net
9、type;N,S,T:integer;F:Text;Procedure Init;初始化过程，读人有向图，并设置流为 0 Var Fn:String;I,J:Integer;Begin Write(Graph File=);Readln(Fn);Assign(F,Fn);Reset(F);Readln(F,N);Fillchar(G,Sizeof(G),0);Fillchar(Lt,Sizeof(Lt),0);For I:=1 To N Do For J:=1 To N Do Read(F,GI,J.C);Close(F);End;Function Find:Integer;寻找已经标号未检查
10、的顶点 Var I:Integer;Begin I:=1;While(I=N)And Not(LtI.L0)And(LtI.P=0)Do Inc(I);If IN Then Find:=0 Else Find:=I;End;Function Ford(Var A:Integer):Boolean;Var 用标号法找增广路径，并求修改量 I,J,M,X:Integer;Begin Ford:=True;Fillchar(Lt,Sizeof(Lt),0);LtS.L:=S;Repeat I:=Find;If i=0 Then Exit;For J:=1 To N Do If(LtJ.L=0)And
11、(GI,J.C0)or(GJ,I.C0)Then Begin if(GI,J.F0)Then LtJ.L:=-I;End;LtI.P:=1;Until(LtT.L0);M:=T;A:=Maxint;Repeat J:=M;M:=Abs(LtJ.L);If LtJ.L0 Then X:=GM,J.C-GM,J.F;If XA Then A:=X;Until M=S;Ford:=False;End;Procedure Change(A:Integer);调整过程 Var M,J:Integer;Begin M:=T;Repeat J:=M;M:=Abs(LtJ.L);If LtJ.L0 Then
12、GM,J.F:=GM,j.F+A;Until M=S;End;Procedure Print;打印最大流及其方案 VAR I,J:Integer;Max:integer;Begin Max:=0;For I:=1 To N DO Begin If GI,T.F0 Then Max:=Max+GI,T.F;For J:=1 To N Do If GI,J.F0 Then Writeln(I,-,J,GI,J.F);End;Writeln(The Max Stream=,Max);End;Procedure Process;求最大流的主过程 Var Del:Integer;Success:Bool
13、ean;Begin S:=1;T:=N;Repeat Success:=Ford(Del);If Success Then Print Else Change(Del);Until Success;End;Begin Main Program Init;Process;End.测试数据文件(zdl.txt)如下:6 0 3 5 0 0 0 0 0 1 4 0 0 0 0 0 0 2 0 0 0 0 0 0 5 0 1 0 3 0 2 0 0 0 0 0 0 运行结果如下:Graph File=zdl.txt 1-2 3 1-3 2 2-4 3 3-5 2 4-6 3 5-6 2 The Max
14、 Stream=5 5.最小费用最大流及算法 上面的网络，可看作为辅送一般货物的运输网络，此时，最大流问题仅表明运输网络运输货物的能力，但没有考虑运送货物的费用。在实际问题中，运送同样数量货物的运输方案可能有多个，因此从中找一个输出费用最小的的方案是一个很重要的问题，这就是最小代价流所要讨论的内容。1.最小费用最大流问题的模型 给定网络 N=(V，E，c，w，s，t)，每一弧(vi,vj)属于 E 上，除了已给容量 cij外，还给了一个单位流量的费用 w(vi,vj)O(简记为 wij)。所谓最小费用最大流问题就是要求一个最大流 f，使得流的总输送费用取最小值。W(f)=wijfij 2.用对
15、偶法解最小费用最大流问题 定义：已知网络 N=(V，E，c，w，s，t)，f 是 N 上的一个可行流，p 为 vs 到 vt(关于流 f)的可增广路径，称 W(p)=wij（p+）-wij（p-）为路径 p 的费用。若 p*是从 vs 到 vt 所有可增广路径中费用最小的路径，则称 p*为最小费用可增广路径。定理：若 f 是流量为 v(f)的最小费用流，p 是关于 f 的从 vs 到 vt 的一条最小费用可增广路径，则 f 经过 p 调整流量 Q 得到新的可行流 f(记为 f=f+Q)，一定是流量为 v(f)+Q 的可行流中的最小费用流。3.对偶法的基本思路 取 f=0 寻找从 vs 到 vt
16、 的一条最小费用可增广路径 p。若不存在 p，则 f 为 N 中的最小费用最大流，算法结束。若存在 p，则用求最大流的方法将 f 调整成 f*，使 v(f*)=v(f)+Q，并将 f*赋值给 f，转。4.迭代法求最小费用可增广路径 在前一节中，我们已经知道了最大流的求法。在最小费用最大流的求解中，每次要找一条最小费用的增广路径，这也是与最大流求法唯一不同之处。于是，对于求最小费用最大流问题余下的问题是怎样寻求关于 f 的最小费用增广路径 p。为此，我们构造一个赋权有向图 b(f)，它的顶点是原网络 N 中的顶点，而把 N 中每一条弧(vi，vj)变成两个相反方向的弧(vi，vj)和(vj，vi
17、)。定义 w(f)中的弧的权如下：如果(fij0)，则bji=-wij；如果(fij=cij)，则bji=+oo 于是在网络 N 中找关于 f 的最小费用增广路径就等价于在赋权有向图 b(f)中，寻求从 vs 到 vt 的最短路径。求最短路有三种经典算法，它们分别是 Dijkstra 算法、Floyd 算法和迭代算法(ford 算法）。由于在本问题中，赋权有向图 b(f)中存在负权，故我们只能用后两种方法求最短路，其中对于本问题最高效的算法是迭代算法。为了程序的实现方便，我们只要对原网络做适当的调整。将原网络中的每条弧(vi，vj)变成两条相反的弧：前向弧(vi,vj)，其容量 cij和费用
18、wij不变，流量为fij；后向弧(vj,vi)，其容量 0 和费用-wij，流量为-fij。事实上，对于原网络的数据结构中，这些单元已存在，在用标号法求最大流时是闲置的。这样我们就不必产生关于流 f 的有向图 b(f)。同时对判断(vi,vj)的流量可否改时，可以统一为判断是否“fij0，则fji=-fij0 then begin Neta,b.c:=c;给弧(a,b)赋容量 c Netb,a.c:=0;给相反弧(b,a)赋容量 0 Neta,b.w:=d;给弧(a,b)赋费用 d Netb,a.w:=-d;给相反孤(b，a)赋费用-d end;until a+b+c+d=0;close(in
19、f);end;function Find_Path:boolean;求最小费用增广路函数,若 bestt.valueMaxInt,则找到增广路，函数返回 true，否则返回 false var Quit:Boolean;i,j:Integer;begin for i:=1 to n do besti.value:=Maxint;bests.value:=0;寻求最小费用增广路径前，给 best 数组赋初值 repeat Quit:=True;for i:=1 to n do if besti.Value Maxint then for j:=1 to n do if(Neti,j.f Neti
20、,j.c)and (besti.value+Neti,j.w bestj.value)then begin bestj.value:=besti.value+Neti,j.w;bestj.fa:=i;Quit:=False;end;until Quit;if bestt.valueMaxint then find_path:=true else find_path:=false;end;procedure Add_Path;var i,j:integer;begin i:=t;while i s do begin j:=besti.fa;inc(Netj,i.f);增广路是弧的数量修改，增量
21、1 Neti,j.f:=-Netj,i.f;给对应相反弧的流量赋值-f i:=j;end;inc(Minw,bestt.value);修改最小总费用的值 end;procedure Out;输出最小费用最大流的费用及方案 var ouf:text;i,j:integer;begin assign(ouf,name2);rewrite(ouf);writeln(ouf,Min w=,Minw);for i:=1 to n do for j:=1 to n do if Neti,j.f 0 then writeln(ouf,i,-,j,:,Neti,j.w,*,Neti,j.f);close(ouf);end;Begin 主程序 Init;while Find_Path do Add_Path;当找到最小费用增广路，修改流 Out;end.flow.in 如下：5 1 2 10 4 1 3 8 1 2 4 2 6 2 5 7 1 3 2 5 2 3 4 10 3 4 5 4 2 0 0 0 0 运行结果 flow.out 如下：Min w=55 1-2:4*3 1-3:1*8 2-5:1*7 3-2:2*4 3-4:3*4 4-5:2*4 练习：1.熟记上述两种算法。2.将例 2 程序中的寻找费用最小增广路径的算法改成 Floyd 算法。