《大流问题的标号》PPT课件.ppt

最大流问题的标号法 Ford-Fulkerson增广路径算法,一、标号法的基本思路,从一个可行流出发（若网络中没有给定F，则可以设F是零流），经过标号过程和调整过程。,1、标号过程,在这个过程中，网络中的顶点或者是标号点（分为已检查和未检查两种），或者是未标号点。每个标号点的标号包含两个部分。第一个标号指明它的标号是从哪一个顶点得到的（前驱指针），以便找出可改进路；第二个标号是为确定可改进量a用的。 标号过程开始，总先给Vs标上（0，+），这时Vs是标号而未检查的顶点，其余都是未标号点。一般地，取一个标号而未检查的顶点Vi，对于一切未标号点Vj： （1）若在弧（vi,vj）上，fijcij,则给vj标号（vi,L(vj)）, L(vj)=minL(vi),Cij-fij。这时顶点vj成为标号而未检查的顶点。,（2）若在弧（vj,vi）上，fji0,则给vj标号（-vi,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的第一标号，直到查到vs为止。这时被找出的弧就构成了可改进路P。令a=L（vt）。调整改进P路上的流量：,并去掉所有的标号，得到新的可行流F=fij,重新进入标号过程，直至检查完所有标号为止。,s,2,1,4,3,t,(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:array1maxn of link;,可改进路的数据类型：将当前已标号点的可改进路存储在数组path中，数据元素为可改进路上的结点，结点信息包括标号（前驱结点指针p，当前可改进量d）和弧指针w: Ptype=record p,d:integer w:link; end; Var path:array1maxn of ptype; 队列：采用宽度优先搜索的方法求最大流。 Var q:array1maxn of integer; op,cl:integer; 队列指针,2、构造网络D的邻接表。 每读入一条弧（u,v）的两个端点u,v及其容量c后，则在Du的邻接表中插入流量为0，容量为c的前向弧（u，v）；在Dv对应的邻接表中插入流量为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:=c Else begin new(x); x.k:=v; x.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 (clnil 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 then Begin 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; End Until 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