最大容量增广路算法课件.ppt

1、1 许多实际问题都可以转化为最大流问题 S ST T最大流问题的例子公路交通网络：车流流量2定义定义6.1 在有向图在有向图G=(V，A)上定义如下的权函数：上定义如下的权函数：（1）L：AR为弧上的权函数，弧为弧上的权函数，弧(i,j)对应的权对应的权 L(i,j)记为记为lij，称为弧称为弧(i,j)的的容量下界容量下界（lower bound）;（2）U：A R为弧上的权函数，弧为弧上的权函数，弧(i,j)对应的权对应的权U(i,j)记为记为uij，称为弧称为弧(i,j)的的容量上界容量上界，或直接称为，或直接称为容量容量（capacity）;（3）D：V R为顶点上的权函数，节点为顶点

2、上的权函数，节点i对应的权对应的权D(i)记为记为di，称为顶点称为顶点i的的供需量供需量（supply/demand）;此时网络可称为此时网络可称为流网络流网络(Flow Network,一般仍简称为一般仍简称为网络网络),),记记为为 N=(V,A,L,U,D).6.1.16.1.1网络中的流网络中的流 di 0:供应点供应点(supply node)(supply node)或源或源(source)(source)、起始点或发货点、起始点或发货点 di 0.10iix在一个无源无汇的流网络中，一个可行流称为可行在一个无源无汇的流网络中，一个可行流称为可行循环流循环流。推论推论 一个可行循

3、环流一定可以表示为至多一个可行循环流一定可以表示为至多m个非零圈流之和个非零圈流之和.如果i1是一个汇点,则找到了从源点指向汇点的一条有向路.否则从i1出发重复上述过程,直到找到一个汇点或再次遇到前面经过的某个顶点时为止,即直到下列两种情况之一出现为止:9当找到一个路流时当找到一个路流时,重新定义使得某个节点的供需量从非零成为重新定义使得某个节点的供需量从非零成为零零,或者使得某条弧的流量从非零成为零或者使得某条弧的流量从非零成为零.当找到一个圈流时当找到一个圈流时,重重新定义使得某条弧的流量从非零成为零新定义使得某条弧的流量从非零成为零.对新网络对新网络,重复上述过程重复上述过程,直到所有顶

4、点变成为转运点直到所有顶点变成为转运点(平衡点平衡点).然后然后,找到一个至少有一条出弧上的流量为正的顶点找到一个至少有一条出弧上的流量为正的顶点,继续重复继续重复上述过程上述过程,这时只有情形这时只有情形(b)会出现会出现,即一定获得一个非零圈流即一定获得一个非零圈流.重复上述过程重复上述过程,直到重新定义的流直到重新定义的流x成为零流为止成为零流为止.(b)找到一个有向圈W.此时,定义(a)找到一条从一个源点找到一条从一个源点i0指向一个汇点指向一个汇点ik的有向路的有向路P.定义定义 PjixddPvijiik),(|min,min)(0.),(),(),(),(00PjiPvxxPvd

5、dPvddijijiiiikk.),(),(WjiWvxxijijWjixWvij),(|min)(上述过程找到路流和圈流的次数之和不会多于上述过程找到路流和圈流的次数之和不会多于m+n次，且其中次，且其中找到圈流的次数不会多于找到圈流的次数不会多于m次次.10单源单汇的网络，可行流单源单汇的网络，可行流x的的流量流量（或（或流值流值）为）为v=v（x）=ds=-dt如果我们并不给定如果我们并不给定ds 和和dt,则网络一般记为则网络一般记为N=（s,t,V,A,U），），容量可行且容量可行且转运点流量守恒的流称为转运点流量守恒的流称为s-t可行流可行流，有时为了方便也称为，有时为了方便也称为

6、可行流可行流.最大流问题最大流问题(Maximum Flow Problem)就是在就是在N=（s,t,V,A,U）中找到流值最中找到流值最大的大的s-t可行流可行流(即即最大流最大流).6.1.2 最大流问题的数学描述最大流问题的数学描述.maxtsv,0,),(:),(:tsitivsivxxAijjjiAjijijAjiuxijij),(,0定理定理6.2(6.2(整流定理整流定理)最大流问题所对应的约束矩阵是全么模最大流问题所对应的约束矩阵是全么模矩阵矩阵.若所有弧容量均为正整数若所有弧容量均为正整数,则问题存在最优整数解则问题存在最优整数解.11引理引理6.1 6.1 任意一个任意一

7、个s-ts-t可行流流值不超过任意一个可行流流值不超过任意一个s-ts-t割容量割容量.6.1.3 增广路定理增广路定理 定义定义6.5 设S，T是网络N=(s,t,V,A,U)中给定的一个割，且sS，t T，则称割S，T为s-t割.s-t割S，T中的弧(i，j)(iS，jT)称为割的前向弧，弧(i,j)(jS，iT)称为割的反向弧.s-t割S，T的容量定义为前向弧的容量之和，记为一个网络中容量最小的s-t割称为最小割.TjSiAjiijuTSU,),(),(),()()0()(TSUuxuxxxxxxxxxxxvijijSiTjijjiSiTjijSiTjjiijSiTjjiijSiSjji

8、ijSiVjjiVjij12增广路增广路引理引理6.2 6.2 如果对于一个可行流存在增广路，则该可行流不是最大流如果对于一个可行流存在增广路，则该可行流不是最大流.定义定义6.6 6.6 设设x x是流网络是流网络N=N=(s s,t t,V V,A A,U U)中给定的可行流，中给定的可行流，P P是一条是一条s-ts-t路，则路，则P P中中满足下列两个条件之一的弧（满足下列两个条件之一的弧（i i，j j）称为）称为增广弧增广弧(augmenting arc)(augmenting arc)：（1 1）弧（）弧（i i，j j）是）是P P的前向弧且为不饱和弧；或的前向弧且为不饱和弧；

9、或（2 2）弧（）弧（i i，j j）是）是P P的反向弧且为非空弧的反向弧且为非空弧.如果如果P P中的弧都是增广弧，则称中的弧都是增广弧，则称P P为关于流为关于流x x的的增广路增广路,简称增广路简称增广路(augmenting path).(augmenting path).这一过程称为这一过程称为x 关于关于P的的增广增广(augmentation)0min,minmin),(),(ijPjiijijPjixxu.),(,),(,),(,PjixPjixPjixxijijijij13证明证明 必要性可以由前面的引理直接得到必要性可以由前面的引理直接得到.下面证明充分性下面证明充分性.

10、定理定理6.3 (增广路定理)一个可行流为最大流的充要条件是不存在增广路.增广路定理增广路定理 假设流网络假设流网络N=(s,t,V,A,U)中不存在关于可行流中不存在关于可行流 x 的增广路的增广路,记网记网络中从络中从 s 出发沿增广弧可以到达的节点集合为出发沿增广弧可以到达的节点集合为S,令令 T=VS,则则sS，tT，即，即 S,T 为为 s-t 割割.并且并且,对于对于A中的任意弧中的任意弧(i,j),如果它是该如果它是该s-t割的前向弧割的前向弧,则则;如果它是该如果它是该s-t割的后向割的后向弧弧,则则=0.ijijux ijx),()(TSUuxxxvSiTjijSiTjjii

11、j引理引理6.16.1证明中的中间结果证明中的中间结果 因此因此,S,T为最小割为最小割,x为最大流为最大流.定理定理6.4 (最大流最小割定理)最大流的流值等于最小割的容量.146.2 6.2 增广路算法增广路算法 6.2.1 Ford-Fulkerson6.2.1 Ford-Fulkerson标号算法标号算法 （）（）基本思想：从任何一个可行流开始基本思想：从任何一个可行流开始,沿增广路对流进行沿增广路对流进行增广增广,直到网络中不存在增广路为止直到网络中不存在增广路为止.问题的关键在于如何有效地找到增广路问题的关键在于如何有效地找到增广路,并保证算法在并保证算法在有限次增广后一定终止有限

12、次增广后一定终止.基本思想：标号过程来寻找网络中的增广路基本思想：标号过程来寻找网络中的增广路predpred（j j）：节点）：节点j j 在可能的增广路中的前一个节点在可能的增广路中的前一个节点;maxfmaxf（j j）:沿该可能的增广路到该节点为止可以增广沿该可能的增广路到该节点为止可以增广的最大流量的最大流量.LIST:LIST:记录可能的增广路上的节点记录可能的增广路上的节点15STEP5.STEP5.转转STEP3.STEP3.STEP3.如果如果LIST 且且maxf（t）=0,继续下一步继续下一步;否则否则:(3a)如果如果 t 已经有标号已经有标号(即即maxf(t)0)，

13、则找到了一条增广路，沿该增广路对，则找到了一条增广路，沿该增广路对流流 x 进行增广进行增广(增广的流量为增广的流量为maxf（t）,增广路可以根据增广路可以根据pred回溯方便地得到回溯方便地得到),转转STEP1.(3b)如果如果 t 没有标号没有标号(即即LIST=且且maxf(t)=0),转转STEP1.STEP4.从从LIST中移走一个节点中移走一个节点i；寻找从节点；寻找从节点i出发的所有可能的增广弧：出发的所有可能的增广弧：(4a)对非饱和前向弧（对非饱和前向弧（i，j），若节点），若节点 j 没有标号没有标号(即即pred（j）=0)，则对，则对j进进行标号，即令行标号，即令m

14、axf(j)=minmaxf(i),uij-xij，pred(j)=i,并将并将j加入加入LIST中中.(4b)对非空反向弧（对非空反向弧（j，i），若节点），若节点 j 没有标号没有标号(即即pred(j)=0)，则对，则对j进行标号，进行标号，令令maxf(j)=minmaxf(i),xji，pred(j)=i,并将并将j加入加入LIST中中.STEP1.若若maxf（t）0,继续下一步继续下一步;否则结束否则结束.STEP0.置初始可行流置初始可行流 x（如零流）（如零流）;对节点对节点 t 标号标号,即令即令maxf（t）=任意正值任意正值（如（如1）.STEP2.取消所有节点取消所有

15、节点 j V 的标号，即令的标号，即令maxf（j）=0,pred（j）=0；令；令LIST=s;对节点对节点 s 标号，即令标号，即令maxf（s）=充分大的正值充分大的正值.16最大流流值为最大流流值为4 4 Ford-FulkersonFord-Fulkerson标号算法标号算法,例：例：（uij，xij）S 15 t2341,11,11,11,01,02,13,13,0S 15 t2341,11,11,11,01,02,23,13,1S 15 t2341,11,11,11,01,12,23,03,217最大流流值为最大流流值为2 2*106Ford-FulkersonFord-Fulk

16、erson标号算法标号算法,例：例：（uij，xij）S 15 t4106,11,1106,0106,1106,05 t24106,01,0106,0106,0106,0S 15 t4106,11,0106,1106,1106,1S 118该算法是否一定在有限步内终止呢？该算法是否一定在有限步内终止呢？如果弧上的容量可以是无理数，可以举出例子说明标号算法不一如果弧上的容量可以是无理数，可以举出例子说明标号算法不一定在有限步内终止；并且，这一增广路算法的极限过程得到的流定在有限步内终止；并且，这一增广路算法的极限过程得到的流的流值即使收敛，也不一定收敛到最大流的流值即使收敛，也不一定收敛到最大流

17、 Ford-FulkersonFord-Fulkerson标号算法标号算法标号算法终止时，网络中一定不再含有增广路标号算法终止时，网络中一定不再含有增广路.如果所有弧上的容量都是正整数，根据整流定理，最大流如果所有弧上的容量都是正整数，根据整流定理，最大流v也也是整数是整数.实际上，由于割实际上，由于割s，Vs中前向弧的条数最多为中前向弧的条数最多为n条，条，因此最大流因此最大流v的上界为的上界为nU（U表示网络中弧上的最大容量）表示网络中弧上的最大容量）.由于每次增广至少使得流值增加由于每次增广至少使得流值增加1个单位，因此增广的次数不个单位，因此增广的次数不会超过会超过v次，算法一定在有限

18、步内终止次，算法一定在有限步内终止.此外，由于每次增广最多需要对所有弧检查一遍，因此算法的此外，由于每次增广最多需要对所有弧检查一遍，因此算法的复杂度为复杂度为O（mv），或表示为），或表示为O（mnU）.伪多项式时间算法，而不是多项式时间算法伪多项式时间算法，而不是多项式时间算法.19定义定义6.7 对网络对网络N=(s,t,V,A,U)中给定的中给定的s-t可行流可行流x，网络，网络N关于流关于流x的的残量网络残量网络N(x)=(s,t,V,A(x),U(x),其中其中A(x),U(x)定义如下：定义如下：（residual network，又常称为增量网络或辅助网络，又常称为增量网络或辅

19、助网络）6.2.2 6.2.2 残量网络残量网络 讨论算法复杂度时，假定讨论算法复杂度时，假定:弧（弧（i，j）A时，弧（时，弧（j，i）A；并假定在残量网络中并假定在残量网络中A（x）=A，也就是说弧的条数和弧集合都，也就是说弧的条数和弧集合都不变不变.这只要允许容量为这只要允许容量为0的弧仍然保留在网络中就可以了的弧仍然保留在网络中就可以了.命题：若命题：若v*是原网络的最大流，则残量网络是原网络的最大流，则残量网络N(x)中最大流为中最大流为 v*-v（x）.0,),(|),(,),(|),()(jiijijxAijjiuxAjijixA,0,),(,),(,)(jijiijijijij

20、ijxAijxuxAjixuxu其中称其中称,uij(x)为弧为弧(i,j)上的上的残留容量残留容量(residual capacity).20残量网络残量网络,例：例：（uij，xij）N(x)中的中的s-t有向路有向路P,对应于原网络对应于原网络N中的一条增广路中的一条增广路；直接称残量网络中的直接称残量网络中的s-t有向路为增广路有向路为增广路.沿沿P可以增广的最大流量称为可以增广的最大流量称为P的的残留容量残留容量.4,14,12,12,12,02,02,22,22,22,21,01,01,11,12,22,22,12,1s st t1 13 31 11 12 22 21 11 12

21、21 11 12 2t ts s21Ford-Fulkerson标号算法每次只是在所有增广路中随便地找一条标号算法每次只是在所有增广路中随便地找一条进行增广进行增广,因此增广的次数可能很多因此增广的次数可能很多.一个自然的想法是一个自然的想法是:如果每次都找一条增广容量最大的增广路如果每次都找一条增广容量最大的增广路,则则总的增广次数应当减少总的增广次数应当减少.这样的算法称为这样的算法称为最大容量增广路算法最大容量增广路算法.6.2.3 6.2.3 最大容量增广路算法最大容量增广路算法S 15 t24106,01,0106,0106,0106,0S 15 t4106,11,1106,0106

22、,1106,022最大容量增广路算法最大容量增广路算法 复杂性分析复杂性分析证明：根据流的分解定理，证明：根据流的分解定理，N(x)中可以找到不超过中可以找到不超过m条从源点条从源点到汇点的有向路（增广路），使得其残留容量之和为到汇点的有向路（增广路），使得其残留容量之和为v*-v（x）.现在考虑从可行流现在考虑从可行流x开始的连续开始的连续2m次最大容量增广：次最大容量增广：(1)如果每次增广的流量都不小于如果每次增广的流量都不小于(v*-v(x)/2m，则，则2m次增广后一定已经达到次增广后一定已经达到了最大流；了最大流；(2)某次增广的流量小于某次增广的流量小于(v*-v(x)/2m,即

23、每经过连续即每经过连续2m次最大容量增广，残量次最大容量增广，残量网络中的最大容量增广路的残留容量至少下降一半网络中的最大容量增广路的残留容量至少下降一半.命题：命题：N(x)中最大容量增广路的残留容量不小于中最大容量增广路的残留容量不小于(v*-v(x)/m.可见可见，最大容量增广路算法将总的增广次数从，最大容量增广路算法将总的增广次数从Ford-Fulkerson标号算法的标号算法的O（nU）降为了）降为了O（mlogU）次）次，因此是一种多项式时间算法，因此是一种多项式时间算法.由于由于最大容量增广路算法最大容量增广路算法每次需要在残量网络中寻找最大容量增广路（可以每次需要在残量网络中寻

24、找最大容量增广路（可以用最短路算法），因此每次增用最短路算法），因此每次增广的时间花费增加了广的时间花费增加了.由于任何增广路的残留容量不会超过由于任何增广路的残留容量不会超过U（U表示网络中弧上的最大容量）且表示网络中弧上的最大容量）且至少为至少为1（这里假设只考虑整数容量网络），因此最多经过（这里假设只考虑整数容量网络），因此最多经过O（2mlogU）=O（mlogU）次最大容量增广，一定已经达到了最大流）次最大容量增广，一定已经达到了最大流.23 (Capacity-Scaling Algorithm)(Capacity-Scaling Algorithm)6.2.4 容量变尺度算法 S

25、TEP3.若若N(x,)不存在不存在s-t 路路,继续下一步继续下一步;否则从否则从N(x,)找到找到一条一条s-t 路路P,沿沿P对当前流进行增广对当前流进行增广,并重复并重复STEP3.STEP1.若若 1,结束结束,已经得到最优解已经得到最优解;否则进行下一步否则进行下一步.STEP2.构造构造 -残量网络残量网络 N(x，).STEP0.置初始可行流置初始可行流 x（如零流）（如零流）;=.Ulog2STEP4.=/2；转；转STEP1.定义：对定义：对N=(s,t,V,A,U)中给定的中给定的s-t可行流可行流x，网络，网络N关于流关于流x的的 -残量网络残量网络N(x，)是其残量网

26、络是其残量网络N(x)的子网络，它由残留容量不的子网络，它由残留容量不小于小于 的弧组成的弧组成.整数容量网络，整数容量网络，N(x，1)=N(x).容量变尺度算法每次都找一条增广容量容量变尺度算法每次都找一条增广容量“充分大充分大”的增广路的增广路,但但不一定最大不一定最大.24容量变尺度算法算法 复杂性分析复杂性分析 的值总共有的值总共有O（logU）种取法）种取法.我们下面说明在给定的我们下面说明在给定的 下，最多执行下，最多执行2m次增广次增广：由于在由于在2-残量网络中已经没有增广路，因此在残量网络中已经没有增广路，因此在-残量残量网络中的最大流不会超过网络中的最大流不会超过2m.因

27、为因为-残量网络中的增残量网络中的增广路的容量至少为广路的容量至少为 ，因此增广次数不会超过，因此增广次数不会超过2m.算法总的增广次数是算法总的增广次数是O（m logU）次，而每次增广路）次，而每次增广路的查找可以采用前面介绍的标号算法，即复杂度为的查找可以采用前面介绍的标号算法，即复杂度为O（m）.因此，算法总复杂度为因此，算法总复杂度为O（m2 logU）.仍不是强多项式时间算法仍不是强多项式时间算法25布 置 作 业（第第1 1讲）讲）目的掌握流网络的基本概念和基本性质；掌握几种典型的增广路算法及复杂性分析内容网络优化网络优化第第184-189页页3;4；5；（第；（第1讲）讲）思考

28、1（1）-（7）；20（不交）（不交）26网网 络络 优优 化化 Network Optimizationhttp:/ 谢金星办公室：理科楼2206#（电话：62787812）Email: http:/ 6章章 最大流问题最大流问题 (Maximum Flow Problem)第第2讲讲27 -概论概论Ford-Fulkerson标号算法每次只是在所有增广路中随便地找一条进行增广标号算法每次只是在所有增广路中随便地找一条进行增广最大容量增广路算法每次都找一条增广容量最大的增广路进行增广最大容量增广路算法每次都找一条增广容量最大的增广路进行增广与最大容量增广路算法对称，一个自然的想法是与最大容量

29、增广路算法对称，一个自然的想法是:如果每次都找一条包含弧如果每次都找一条包含弧数最少的增广路（称为最短增广路）数最少的增广路（称为最短增广路）,则算法效果如何？则算法效果如何？这样的算法称为最这样的算法称为最短增广路算法短增广路算法 本节主要结果之一本节主要结果之一：最短增广路算法最多经过：最短增广路算法最多经过O（mn）次增广后终止）次增广后终止.对于这时特殊的最短路问题对于这时特殊的最短路问题,我们可以很容易构造最短路算法在我们可以很容易构造最短路算法在O（m）的时）的时间内找到一条最短增广路间内找到一条最短增广路(例如可以采用从节点例如可以采用从节点s或或t开始的广度优先搜索方开始的广度

30、优先搜索方法法)，因此这种实现方法的复杂度为，因此这种实现方法的复杂度为O（m2n）.本节主要结果之二本节主要结果之二：在在O（n）的时间内找到一条最短增广路，即算法复杂度）的时间内找到一条最短增广路，即算法复杂度为为O（mn2）从目前已有的理论分析和计算经验来看，最短增广路算法是所有增广路算法从目前已有的理论分析和计算经验来看，最短增广路算法是所有增广路算法中效果最好的算法，可以设计出中效果最好的算法，可以设计出在在O（logn）的平均时间内找到一条最短增）的平均时间内找到一条最短增广路，即算法复杂度为广路，即算法复杂度为O（mnlogn）6.3 6.3 最短增广路算法最短增广路算法28定义

31、定义6.8 对于一个残量网络对于一个残量网络N（x），如果一个函数），如果一个函数d 将节点集合将节点集合V映射到非负映射到非负整数集合，则称整数集合，则称d是关于残量网络是关于残量网络N（x）的距离函数（）的距离函数（distance function），），d（i）称为节点）称为节点 i 的的距离标号距离标号（distance label）.如果距离函数如果距离函数d满足：满足：（1）d（t）=0，（2）对）对N（x）中的任意一条弧（）中的任意一条弧（i，j）有）有d（i）d（j）+1，则称距离函数则称距离函数 d 关于流关于流 x 是是有效的有效的（valid），或称距离标号（），或称距

32、离标号（函数）函数）d 是是有效的有效的.如果任意一个节点的距离标号正好等于残量网络中从该节点到汇点（节点如果任意一个节点的距离标号正好等于残量网络中从该节点到汇点（节点t t）的所有有向路中弧数最少的有向路所包含的弧数的所有有向路中弧数最少的有向路所包含的弧数(当令所有弧的长度为当令所有弧的长度为1 1时时,这就是从该节点到汇点的最短路路长这就是从该节点到汇点的最短路路长,因此我们后面直接称为最短路路长因此我们后面直接称为最短路路长)，则称距离函数则称距离函数d d关于流关于流x x是是精确的精确的(exact)(exact)，或称距离标号是精确的，或称距离标号是精确的.如果对如果对N N（

33、x x）中的某一条弧（）中的某一条弧（i i，j j）有）有d（i）=d（j）+1+1，则称弧，则称弧（i i，j j）为）为允许弧允许弧(Admissible Arc).(Admissible Arc).一条一条s-ts-t有向路如果完全由有向路如果完全由允许弧组成允许弧组成,则该有向路称为则该有向路称为允许路允许路(Admissible Path).(Admissible Path).6.3.1 6.3.1 距离标号距离标号精确的距离标号一定是有效的精确的距离标号一定是有效的.29有效的有效的 距离标号距离标号 0 00 01 11 11 1s st t1 10 01 12 22 2s s

34、t t精确的精确的 对于一个残量网络对于一个残量网络N（x），如何确定其精确的距离标号呢？），如何确定其精确的距离标号呢？从汇点（节点从汇点（节点t）开始，对）开始，对N（x）沿反向弧进行广度优先搜索）沿反向弧进行广度优先搜索这一过程的复杂度为这一过程的复杂度为O（m）.可以看出，一个节点的精确的距离标号实际上表示的是从该节可以看出，一个节点的精确的距离标号实际上表示的是从该节点到汇点（节点点到汇点（节点t）的最短路路长，也就是说对所有节点按照最）的最短路路长，也就是说对所有节点按照最短路路长进行了层次划分短路路长进行了层次划分.30距离标号距离标号 性质性质 引理引理6.3 若距离函数若距离

35、函数d是有效的，则：是有效的，则：（1）d（i）是残量网络）是残量网络N（x）中从节点）中从节点i到节点到节点t的最短有向路的最短有向路路长的下界路长的下界.（2）如果）如果d（s）n，则残量网络，则残量网络N（x）中从节点）中从节点s到节点到节点t没没有有向路有有向路(增广路增广路).（3）允许路是残量网络）允许路是残量网络N（x）中的最短增广路）中的最短增广路.1 12 21 14 4s s1 10 01 12 22 2t t3 331STEP0.(预处理预处理)置初始可行流置初始可行流x为零流为零流;计算精确的距离函计算精确的距离函数数d；令当前节点；令当前节点i=s.STEP1.若若d

36、（s）0 时时令令d(i)=mind(j)+1|(i，j)A(x)且且uij(x)0,否则令否则令d（i）=n;且当且当i s时再令时再令i=pred(i).转转STEP1.“前进步前进步”“回退步回退步”6.3.2 最短增广路算法最短增广路算法326.3.2 最短增广路算法最短增广路算法 性质性质 引理引理6.4 6.4 在最短增广路算法中在最短增广路算法中,距离标号始终保持是有效的距离标号始终保持是有效的.归纳法：归纳法：在预处理阶段，构造的距离标号是有效的在预处理阶段，构造的距离标号是有效的.只需证明只需证明一次增广操作和一次重新标号操作不改变距离标号的有效性一次增广操作和一次重新标号操

37、作不改变距离标号的有效性.增广操作可能引起残量网络的弧的变化只有两种情况：增广操作可能引起残量网络的弧的变化只有两种情况：允许路上的弧允许路上的弧(i，j)可能退出残量网络可能退出残量网络:这不会影响这不会影响(i，j)弧的端点上的距弧的端点上的距离标号的有效性；离标号的有效性；(j，i)弧可能进入残量网络弧可能进入残量网络:由于由于(i，j)弧是允许弧，弧是允许弧，因此因此d(i)=d(j)+1，所以所以d(j)=d(i)-10:不会破坏任意的不会破坏任意的(i，j)弧的端点上的距离标号的有效性弧的端点上的距离标号的有效性;重新标号时节点重新标号时节点i在残量网络中没有允许弧在残量网络中没有

38、允许弧,即对于任意的即对于任意的(i，j)N(x)满满足足d(i)d(i),即标号严格增加即标号严格增加.对于任意的对于任意的(j，i)弧弧,d(j)d(i)+1 d(i)+1，仍，仍有效有效336.3.2 最短增广路算法最短增广路算法 性质性质 推论：推论：由于距离函数是有效的，算法结束时残量网络由于距离函数是有效的，算法结束时残量网络N N（x x）中）中从节点从节点s s到节点到节点t t没有允许路没有允许路,即残量网络中不存在增广路即残量网络中不存在增广路,所以所以算法确实求到了最大流算法确实求到了最大流 例例6.5 6.5 用最短增广路算法计算如下网络图用最短增广路算法计算如下网络图

39、6.56.5（a a）中的最大流）中的最大流（s=1s=1，t=4t=4，弧上数字表示容量），弧上数字表示容量）.1 12 23 34 41 12 23 34 45 51 12 23 34 41 12 23 34 45 51 11 12 20 0341 12 23 34 41 12 23 34 41 11 12 23 34 41 12 24 41 14 40 01 11 12 21 11 12 23 34 41 11 13 34 41 14 41 10 01 12 21 12 23 34 41 12 21 14 45 51 12 23 34 41 12 21 14 45 52 20 01 12

40、 23 31 12 23 34 41 12 21 14 45 51 12 23 34 41 12 21 14 45 52 20 01 12 24 435最短增广路算法最短增广路算法 首先思考：如何从一个节点出发找到从该节点出发的一条允许弧？首先思考：如何从一个节点出发找到从该节点出发的一条允许弧？数据结构：即对每个节点数据结构：即对每个节点i，算法用链表，算法用链表A（i）记录该节点出发的所有弧，）记录该节点出发的所有弧，这些弧的顺序可以任意，但一旦确定以后在算法执行过程中就不再改变这些弧的顺序可以任意，但一旦确定以后在算法执行过程中就不再改变.当前弧当前弧（Current-Arc）:对每个节

41、点对每个节点i，用一个指针指向下一条将要被检索，用一个指针指向下一条将要被检索的弧，这条弧称为当前弧的弧，这条弧称为当前弧.算法开始时，当前弧为算法开始时，当前弧为A（i）中的第一条弧。）中的第一条弧。在查找从该节点出发的允许弧时，总是从当前弧开始判别：如果当前弧是允在查找从该节点出发的允许弧时，总是从当前弧开始判别：如果当前弧是允许弧，则返回这条弧；否则令许弧，则返回这条弧；否则令A（i）中的下一条弧为当前弧。）中的下一条弧为当前弧。如此下去，直到找到一条允许弧或判别完如此下去，直到找到一条允许弧或判别完 A（i）的最后一条弧为止。）的最后一条弧为止。6.3.3 复杂度分析 1 12 24

42、42 22 23 31 12 23 34 45 56 60 05 54 410100 0初始当前弧初始当前弧:(1,2):(1,2)当前弧当前弧:(3,4):(3,4)分析：即确定分析：即确定“前进步前进步”、“回退步回退步”、增广、重标号的次数及每次的复杂、增广、重标号的次数及每次的复杂度度36最短增广路算法最短增广路算法 采用当前弧（采用当前弧（Current-Arc）结构时：）结构时：如果如果 A（i）中的一条弧在以前的迭代中不是允许弧，则在节点）中的一条弧在以前的迭代中不是允许弧，则在节点i的标号改变之前它仍然不是允许弧的标号改变之前它仍然不是允许弧.Why?非允许弧非允许弧(i,j)

43、的两种情况：的两种情况：(1)uij(x)=0;(2)d(i)0的节点的节点i()称为称为活跃的活跃的(Active).)()(),(:),(:VixxieAjijijAijjjitsi,42STEP1.STEP1.如果残量网络中不存在活跃节点如果残量网络中不存在活跃节点,结束结束,已经得到最优已经得到最优解解;否则继续否则继续.6.4.1 6.4.1 一般的预流推进算法一般的预流推进算法 正确性：算法的每次迭代是一次推进操作正确性：算法的每次迭代是一次推进操作(STEP2的前面部分的前面部分)或者一次重新或者一次重新标号操作标号操作(STEP2的后面部分的后面部分).如果推进的流量等于弧上的

44、残留容量如果推进的流量等于弧上的残留容量,则称为则称为饱和推进饱和推进(saturating push),否则否则称为称为非饱和推进非饱和推进(nonsaturating push).算法预处理阶段已经令距离标号算法预处理阶段已经令距离标号d（s）=n,网络中永远不会有增广路存在网络中永远不会有增广路存在.当算法终止时当算法终止时,网络中不含有活跃节点网络中不含有活跃节点,此时得到的预流实际上已经是一个可此时得到的预流实际上已经是一个可行流行流.因此是最大流。因此是最大流。STEP0.(预处理预处理)置初始可行流置初始可行流x为零流为零流;对节点对节点s的每条出弧的每条出弧（s，j）令）令 ;

45、对任意的对任意的 i V 计算精确的距离标号计算精确的距离标号d（i）；）；令令d（s）=n.sjsjuxSTEP2.在网络中选取活跃节点在网络中选取活跃节点i；如果存在节点；如果存在节点i的某条出弧的某条出弧(i,j)为允许弧，则将为允许弧，则将 个单位的流从节点个单位的流从节点i推进到节点推进到节点j；否则令否则令d（i）=mind(j)+1|(i,j)A(x)且且 0.转转STEP1.)(),(minxuieij)(xuij436.4.1 6.4.1 一般的预流推进算法一般的预流推进算法例例6.8 6.8 用预流推进算法计算如下图用预流推进算法计算如下图6.86.8网络（网络（a a）中

46、的最大流）中的最大流（弧上数字表示容量）（弧上数字表示容量）.s=1,t=4.s=1,t=41 12 23 34 41 13 33 34 45 51 12 23 34 41 13 33 34 45 53,13,14,14,1-7,4-7,40,00,0e（i）,d（i）446.4.1 6.4.1 一般的预流推进算法一般的预流推进算法1 12 23 34 41 13 33 34 45 52,12,14,14,1-7,4-7,41,01,01 12 23 34 41 13 33 34 41 12,22,20,10,1-7,4-7,45,05,04 41,11,11 12 23 34 41 13 3

47、2 24 45 50,20,2-7,4-7,46,06,01 11 12 23 34 41 13 32 24 41 10,20,22,12,1-7,4-7,45,05,01 14 4456.4.1 6.4.1 一般的预流推进算法一般的预流推进算法1 12 23 34 41 13 34 45 51,21,20,30,3-7,4-7,45,05,01 13 31 14 45 51,21,20,30,3-7,4-7,45,05,01 13 32 24 45 51,21,20,30,3-7,4-7,46,06,01 12 23 34 41 13 32 24 40,40,41,31,3-7,4-7,46

48、,06,05 51 11 12 23 34 41 13 32 23 35 50,40,40,50,5-6,4-6,46,06,01 11 1最大流最大流1 12 23 34 41 13 32 23 35 546一般的预流推进算法一般的预流推进算法 引理引理6.8 6.8 在预流推进算法中在预流推进算法中,距离标号始终保持是有效的距离标号始终保持是有效的.归纳法归纳法 在预处理阶段，构造的距离标号是有效的在预处理阶段，构造的距离标号是有效的.只需证明：只需证明：算法的一次推进和一次重新标号不会改变距离标号的有效性算法的一次推进和一次重新标号不会改变距离标号的有效性.一次沿允许弧（一次沿允许弧（i

49、，j）的推进操作可能引起残量网络弧的变化只有两种情况：）的推进操作可能引起残量网络弧的变化只有两种情况：（i，j）弧可能退出残量网络（饱和推进），不影响距离标号的有效性；）弧可能退出残量网络（饱和推进），不影响距离标号的有效性；（j，i）弧可能进入残量网络，由于）弧可能进入残量网络，由于(i，j)弧是允许弧，因此弧是允许弧，因此 d(i)=d(j)+1，所以所以d（j）=d（i）-10.显然显然,这不会破坏任意的这不会破坏任意的(i，j)弧的端点上的距离标号的有效性弧的端点上的距离标号的有效性.由于重新标号时节点由于重新标号时节点i在残量网络中没有允许弧在残量网络中没有允许弧,也就是说对于任意

50、的也就是说对于任意的(i，j)弧满足弧满足d(i)d(i),即标号严格增加即标号严格增加.对于任意的对于任意的(j,i)弧弧,d(j)d(i)+1 d(i)+1,因此也不会破坏任何因此也不会破坏任何(j,i)弧的端点弧的端点上的距离标号的有效性上的距离标号的有效性.分析：分析：首先证明一些基本的结论首先证明一些基本的结论（引理）（引理）6.4.2 复杂度分析47一般的预流推进算法一般的预流推进算法 引理引理6.9 6.9 在预流推进算法的执行过程中在预流推进算法的执行过程中,在残量网络上在残量网络上,从任何一从任何一个活跃节点到源点个活跃节点到源点s s都存在一条有向路都存在一条有向路.证明证