《大流问题的标号》由会员分享,可在线阅读,更多相关《大流问题的标号(13页珍藏版)》请在金锄头文库上搜索。
1、最大流问题的标号法Ford-Fulkerson增广路径算法一、标号法的基本思路从一个可行流出发(若网络中没有给定F,则可以设F是零流),经过标号过程和调整过程。1、标号过程在这个过程中,网络中的顶点或者是标号点(分为已检查和未检查两种),或者是未标号点。每个标号点的标号包含两个部分。第一个标号指明它的标号是从哪一个顶点得到的(前驱指针),以便找出可改进路;第二个标号是为确定可改进量a用的。标号过程开始,总先给Vs标上(0,+),这时Vs是标号而未检查的顶点,其余都是未标号点。一般地,取一个标号而未检查的顶点Vi,对于一切未标号点Vj:(1)若在弧(vi,vj)上,fij0,则给vj标号(-vi
2、,L(vj)), L(vj)=minL(vi),fji。这时顶点vj成为标号而未检查的顶点。在vi的全部相邻顶点都已标号后,vi成为标号而已检查过的顶点。重复上述步骤,一旦vt被标上号,表明得到一条从vs到vt的可改进路P,转入调整过程;若所有标号都已检查过致使标号过程无法继续时,则算法结束。这时的可行流即最大流。2、调整过程采用“倒向追踪”的方法,从vt开始,利用标号点的第一个标号逐条弧地找出可改进路P,并以vt的第二个标号L(vt)作为改进量a,改进P路上的流量。例如设vt的第一个标号为vk(或-vk),则弧(vk,vt)(或相应的弧(vt,vk)是P上的弧。接下来检查vk的第一标号,直到
3、查到vs为止。这时被找出的弧就构成了可改进路P。令a=L(vt)。调整改进P路上的流量:并去掉所有的标号,得到新的可行流F=fij,重新进入标号过程,直至检查完所有标号为止。s2143t(5,1)(3,3)(4,3)(2,2)(2,1)(5,3)(1,1)(1,1)(3,0)弧旁的数字是(cij,fij)二、标号法的算法流程1、数据结构:采用邻接表D存储。Const maxn=xxx;Type link=dtype; dtype=record k:integer; 顶点序号 f,c:integer; 流量,容量 next,pre:link; 后向弧指针,前向弧指针 end;Var d:arra
4、y1.maxn of link;可改进路的数据类型:将当前已标号点的可改进路存储在数组path中,数据元素为可改进路上的结点,结点信息包括标号(前驱结点指针p,当前可改进量d)和弧指针w:Ptype=record p,d:integer w:link; end;Var path:array1.maxn of ptype;队列:采用宽度优先搜索的方法求最大流。Var q:array1.maxn of integer; op,cl:integer; 队列指针2、构造网络D的邻接表。每读入一条弧(u,v)的两个端点u,v及其容量c后,则在Du的邻接表中插入流量为0,容量为c的前向弧(u,v);在Dv
5、对应的邻接表中插入流量为0,容量为0的后向弧(v,u)。这个过程可以用子过程insert(u,v,c)完成。构造过程:读定点数n,源点序号s和汇点序号t;For i:=1 to n do di:=nil;While D网未读完 do begin 读入当前弧的两个端点u,v及其容量c; insert(u,v,c); end;Procedure insert(u,v,c:integer);Var x:link;Begin x:=du;While (xnil) and(x.kv) do x:=x.next;If xnil then x.c:=cElse begin new(x); x.k:=v; x
6、.c:=c; x.f:=0; x.next:=du; du:=x; new(x.g); x.g.k:=u; x.g.c:=0; x.g.f:=0; x.g.g:=x; x.g.next:=dv; dv:=x.g; end;3、采用宽度优先搜索求最大流。Procedure ford;Var u,a:integer; x:link;Begin repeat fillchar(path,sizeof(path),0); paths.d:=maxint; paths.p=s; cl:=0; op:=1; qop:=s; while (clop) and(patht.p=0) do begin inc(
7、cl); u:=qcl; x:=du; while xnil do begin a:=x.c-x.f; if (pathx.k.p=0) and (a0) then begin inc(op); qop:=x.k; pathx.k.p:=u; pathx.k.w:=x; if pathu.da then pathx.k.d:=pathu.d else pathx.k.d:=a; end; x:=x.next; end; end;If patht.p0 thenBegin u:=t; a:=pathu.d; repeat pathu.w.f:=pathu.w.f+a; pathu.w.g.f:=-pathu.w.f; u:=pathu.p; until u=s;EndUntil patht.p=0;End; 4、输出最大流的流量Procedure answer;Var I,tot:integer; x:link;Begin tot:=0; for i:=1 to n do begin x:=di; while xnil do begin if x.f0 then 输出弧(i,x.k)及其流量x.f; if (i=s) and (x.f0) then tot:=tot+x.f; x:=x.next; end; end;输出最大流量tot;End;