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

《《大流问题的标号》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最大流问题的标号法Ford-Fulkerson增广路径算法一、标号法的基本思路从一个可行流出发（若网络中没有给定F，则可以设F是零流），经过标号过程和调整过程。1、标号过程在这个过程中，网络中的顶点或者是标号点（分为已检查和未检查两种），或者是未标号点。每个标号点的标号包含两个部分。第一个标号指明它的标号是从哪一个顶点得到的（前驱指针），以便找出可改进路；第二个标号是为确定可改进量a用的。标号过程开始，总先给Vs标上（0，+∞），这时Vs是标号而未检查的顶点，其余都是未标号点。一般地，取一个标号而未检查的顶点Vi，对于一切未标号点V

2、j：（1）若在弧（vi,vj）上，fij0,则给vj标号（-vi,L(vj)）,L(vj)=min{L(vi),fji}。这时顶点vj成为标号而未检查的顶点。在vi的全部相邻顶点都已标号后，vi成为标号而已检查过的顶点。重复上述步骤，一旦vt被标上号，表明得到一条从vs到vt的可改进路P，转入调整过程；若所有标号都已检查过致使标号过程无法继续时，则算法结束。这时的可行

3、流即最大流。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’},重新进入标号过程，直至检查完所有标号为止。s2143t(5,1)(3,3)(4,3)(2,2)(2,

4、1)(5,3)(1,1)(1,1)(3,0)弧旁的数字是（cij,fij）二、标号法的算法流程1、数据结构：采用邻接表D存储。Constmaxn=xxx;Typelink=^dtype;dtype=recordk:integer;{顶点序号}f,c:integer;{流量，容量}next,pre:link;{后向弧指针，前向弧指针}end;Vard:array[1..maxn]oflink;可改进路的数据类型：将当前已标号点的可改进路存储在数组path中，数据元素为可改进路上的结点，结点信息包括标号（前驱结点指针p，当前可改进量d）

5、和弧指针w:Ptype=recordp,d:integerw:link;end;Varpath:array[1..maxn]ofptype;队列：采用宽度优先搜索的方法求最大流。Varq:array[1..maxn]ofinteger;op,cl:integer;{队列指针}2、构造网络D的邻接表。每读入一条弧（u,v）的两个端点u,v及其容量c后，则在D[u]的邻接表中插入流量为0，容量为c的前向弧（u，v）；在D[v]对应的邻接表中插入流量为0，容量为0的后向弧（v,u）。这个过程可以用子过程insert(u,v,c)完成。构造

6、过程：读定点数n，源点序号s和汇点序号t；Fori:=1tondod[i]:=nil;WhileD网未读完dobegin读入当前弧的两个端点u,v及其容量c；insert(u,v,c)；end;Procedureinsert(u,v,c:integer);Varx:link;Beginx:=d[u];While(x<>nil)and(x^.k<>v)dox:=x^.next;Ifx<>nilthenx^.c:=cElsebeginnew(x);x^.k:=v;x^.c:=c;x^.f:=0;x^.next:=d[u];d[u]:=x

7、;new(x^.g);x^.g^.k:=u;x^.g^.c:=0;x^.g^.f:=0;x^.g^.g:=x;x^.g^.next:=d[v];d[v]:=x^.g;end;3、采用宽度优先搜索求最大流。Procedureford;Varu,a:integer;x:link;Beginrepeatfillchar(path,sizeof(path),0);path[s].d:=maxint;path[s].p=s;cl:=0;op:=1;q[op]:=s;while(cl

8、cl);u:=q[cl];x:=d[u];whilex<>nildobegina:=x^.c-x^.f;if(path[x^.k].p=0)and(a>0)thenbegininc(op);q[op]:=x^.k;path[x^.k]