最大流问题(数学建模资料).ppt

网网 络络 优优 化化 Network Optimizationhttp:/ 谢金星办公室：理科楼1308#（电话：62787812）Email: http:/ 6章章 最大流问题最大流问题 (Maximum Flow Problem)第第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为顶点上的权函数，节点为顶点上的权函数，节点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.在一个无源无汇的流网络中，一个可行流称为可行在一个无源无汇的流网络中，一个可行流称为可行循环流循环流。推论推论 一个可行循环流一定可以表示为至多一个可行循环流一定可以表示为至多m个非零圈流之和个非零圈流之和.如果i1是一个汇点,则找到了从源点指向汇点的一条有向路.否则从i1出发重复上述过程,直到找到一个汇点或再次遇到前面经过的某个顶点时为止,即直到下列两种情况之一出现为止:9当找到一个路流时当找到一个路流时,重新定义使得某个节点的供需量从非零成重新定义使得某个节点的供需量从非零成为零为零,或者使得某条弧的流量从非零成为零或者使得某条弧的流量从非零成为零.当找到一个圈流当找到一个圈流时时,重新定义使得某条弧的流量从非零成为零重新定义使得某条弧的流量从非零成为零.对新网络对新网络,重复上述过程重复上述过程,直到所有顶点变成为转运点直到所有顶点变成为转运点(平衡点平衡点).然然后后,找找到到一一个个至至少少有有一一条条出出弧弧上上的的流流量量为为正正的的顶顶点点,继继续续重重复复上上述述过过程程,这这时时只只有有情情形形(b)(b)会会出出现现,即即一一定定获获得得一一个个非非零零圈圈流流.重复上述过程重复上述过程,直到重新定义的流直到重新定义的流x x成为零流为止成为零流为止.(b)(b)找到一个有向圈W.此时,定义(a)(a)找到一条从一个源点找到一条从一个源点i i0 0指向一个汇点指向一个汇点i ik k的有向路的有向路P P.定义定义 上述过程找到路流和圈流的次数之和不会多于上述过程找到路流和圈流的次数之和不会多于m m+n n次，且其中找次，且其中找到圈流的次数不会多于到圈流的次数不会多于m m次次.10单源单汇的网络，可行流单源单汇的网络，可行流x的的流量流量（或（或流值流值）为）为v=v（x）=ds=-dt如果我们并不给定如果我们并不给定ds 和和dt,则网络一般记为则网络一般记为N=（s,t,V,A,U），），容量可行且容量可行且转运点流量守恒的流称为转运点流量守恒的流称为s-t可行流可行流，有时为了方便也称为，有时为了方便也称为可行流可行流.最大流问题最大流问题(Maximum Flow Problem)就是在就是在N=（s,t,V,A,U）中找到流值最大中找到流值最大的的s-t可行流可行流(即即最大流最大流).6.1.2 最大流问题的数学描述最大流问题的数学描述 定理定理6.2(6.2(整流定理整流定理)最大流问题所对应的约束矩阵是全么模最大流问题所对应的约束矩阵是全么模矩阵矩阵.若所有弧容量均为正整数若所有弧容量均为正整数,则问题存在最优整数解则问题存在最优整数解.11引理引理6.1 6.1 任意一个任意一个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割称为最小割.12增广路增广路引理引理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的前向弧且为不饱和弧；或的前向弧且为不饱和弧；或（2 2）弧（）弧（i i，j j）是）是P P的反向弧且为非空弧的反向弧且为非空弧.如如果果P P中中的的弧弧都都是是增增广广弧弧，则则称称P P为为关关于于流流x x的的增增广广路路,简简称称增增广广路路(augmenting path).(augmenting path).这一过程称为这一过程称为x 关于关于P的的增广增广(augmentation)13证明证明 必要性可以由前面的引理直接得到必要性可以由前面的引理直接得到.下面证明充分性下面证明充分性.定定理理6.3 (增广路定理)一个可行流为最大流的充要条件是不存在增广路.增广路定理增广路定理 假设流网络假设流网络N=N=(s s,t t,V V,A A,U U)中不存在关于可行流中不存在关于可行流x x的增广路的增广路,记记网络中从网络中从s s出发沿增广弧可以到达的节点集合为出发沿增广弧可以到达的节点集合为S S,令令T T=VSVS,则则s sS S，t tT T，即，即S,TS,T为为s-ts-t割割.并且并且,对于对于A A中的任意弧中的任意弧(i,ji,j),),如果它是该如果它是该s-ts-t割的前向弧割的前向弧,则则;如果它是该如果它是该s-ts-t割的后向割的后向弧弧,则则=0.=0.引理引理6.16.1证明中的中间结果证明中的中间结果 因此因此,S,TS,T 为最小割为最小割,x x为最大流为最大流.定理定理6.4 (最大流最小割定理)最大流的流值等于最小割的容量.146.2 6.2 增广路算法增广路算法 6.2.1 Ford-Fulkerson6.2.1 Ford-Fulkerson标号算法标号算法 （）（）基基本本思思想想：从从任任何何一一个个可可行行流流开开始始,沿沿增增广广路路对对流流进进行行增广增广,直到网络中不存在增广路为止直到网络中不存在增广路为止.问问题题的的关关键键在在于于如如何何有有效效地地找找到到增增广广路路,并并保保证证算算法法在在有限次增广后一定终止有限次增广后一定终止.基本思想：标号过程来寻找网络中的增广路基本思想：标号过程来寻找网络中的增广路predpred（j j）：节点）：节点j j 在可能的增广路中的前一个节点在可能的增广路中的前一个节点;maxfmaxf（j j）:沿沿该该可可能能的的增增广广路路到到该该节节点点为为止止可可以以增增广广的最大流量的最大流量.LIST:LIST:记录可能的增广路上的节点记录可能的增广路上的节点15STEP5.STEP5.转转STEP3.STEP3.STEP3.如果如果LIST 且且maxf（t）=0,继续下一步继续下一步;否则否则:(3a)如如果果 t 已已经经有有标标号号(即即maxf(t)0)，则则找找到到了了一一条条增增广广路路，沿沿该该增增广广路路对对流流 x 进进行行增增广广(增增广广的的流流量量为为maxf（t）,增增广广路路可可以以根根据据pred回回溯溯方方便便地地得得到到),转转STEP1.(3b)如果如果 t 没有标号没有标号(即即LIST=且且maxf(t)=0),转转STEP1.STEP4.从从LIST中移走一个节点中移走一个节点i；寻找从节点；寻找从节点i出发的所有可能的增广弧：出发的所有可能的增广弧：(4a)对对非非饱饱和和前前向向弧弧（i，j），若若节节点点 j 没没有有标标号号(即即pred（j）=0)，则则对对j进进行标号，即令行标号，即令maxf(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.取取消消所所有有节节点点 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-Fulkerson标号算法标号算法,例：例：（uij，xij）S 15 t4106,11,1106,0106,1106,05 t24106,01,0106,0106,0106,0S 15 t4106,11,0106,1106,1106,1S 118该算法是否一定在有限步内终止呢？该算法是否一定在有限步内终止呢？如如果果弧弧上上的的容容量量可可以以是是无无理理数数，可可以以举举出出例例子子说说明明标标号号算算法法不不一一定定在在有有限限步步内内终终止止；并并且且，这这一一增增广广路路算算法法的的极极限限过过程程得得到到的的流流的流值即使收敛，也不一定收敛到最大流的流值即使收敛，也不一定收敛到最大流 Ford-FulkersonFord-Fulkerson标号算法标号算法标号算法终止时，网络中一定不再含有增广路标号算法终止时，网络中一定不再含有增广路.如如果果所所有有弧弧上上的的容容量量都都是是正正整整数数，根根据据整整流流定定理理，最最大大流流v也也是是整整数数.实实际际上上，由由于于割割s，Vs中中前前向向弧弧的的条条数数最最多多为为n条条，因此最大流因此最大流v的上界为的上界为nU（U表示网络中弧上的最大容量）表示网络中弧上的最大容量）.由由于于每每次次增增广广至至少少使使得得流流值值增增加加1个个单单位位，因因此此增增广广的的次次数数不不会超过会超过v次，算法一定在有限步内终止次，算法一定在有限步内终止.此此外外，由由于于每每次次增增广广最最多多需需要要对对所所有有弧弧检检查查一一遍遍，因因此此算算法法的的复杂度为复杂度为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，又常称为增量网络或辅助网络，又常称为增量网络或辅助网络）6.2.2 6.2.2 残量网络残量网络 讨讨论论算算法法复复杂杂度度时时，假假定定:弧弧（i，j）A时时，弧弧（j，i）A；并并假假定定在在残残量量网网络络中中A（x）=A，也也就就是是说说弧弧的的条条数数和和弧弧集集合合都都不变不变.这只要允许容量为这只要允许容量为0的弧仍然保留在网络中就可以了的弧仍然保留在网络中就可以了.命题：若命题：若v*是原网络的最大流，则残量网络是原网络的最大流，则残量网络N(x)中最大流为中最大流为 v*-v（x）.其中称其中称,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 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,1106,022最大容量增广路算法最大容量增广路算法 复杂性分析复杂性分析证证明明：根根据据流流的的分分解解定定理理，N(x)中中可可以以找找到到不不超超过过m条条从从源源点点到汇点的有向路（增广路），使得其残留容量之和为到汇点的有向路（增广路），使得其残留容量之和为v*-v（x）.现在考虑从可行流现在考虑从可行流x开始的连续开始的连续2m次最大容量增广：次最大容量增广：(1)如如果果每每次次增增广广的的流流量量都都不不小小于于(v*-v(x)/2m，则则2m次次增增广广后后一一定定已已经经达达到了最大流；到了最大流；(2)某某次次增增广广的的流流量量小小于于(v*-v(x)/2m,即即每每经经过过连连续续2m次次最最大大容容量量增增广广，残残量网络中的最大容量增广路的残留容量至少下降一半量网络中的最大容量增广路的残留容量至少下降一半.命题：命题：N(x)中最大容量增广路的残留容量不小于中最大容量增广路的残留容量不小于(v*-v(x)/m.可可见见，最最大大容容量量增增广广路路算算法法将将总总的的增增广广次次数数从从Ford-Fulkerson标标号号算算法法的的O（nU）降为了）降为了O（mlogU）次）次，因此是一种多项式时间算法，因此是一种多项式时间算法.由由于于最最大大容容量量增增广广路路算算法法每每次次需需要要在在残残量量网网络络中中寻寻找找最最大大容容量量增增广广路路（可可以以用最短路算法），因此每次增用最短路算法），因此每次增广的时间花费增加了广的时间花费增加了.由由于于任任何何增增广广路路的的残残留留容容量量不不会会超超过过U（U表表示示网网络络中中弧弧上上的的最最大大容容量量）且且至至少少为为1（这这里里假假设设只只考考虑虑整整数数容容量量网网络络），因因此此最最多多经经过过O（2mlogU）=O（mlogU）次最大容量增广，一定已经达到了最大流）次最大容量增广，一定已经达到了最大流.23 (Capacity-Scaling Algorithm)(Capacity-Scaling Algorithm)6.2.4 容量变尺度算法 STEP3.若若N(x,)不不存存在在s-t 路路,继继续续下下一一步步;否否则则从从N(x,)找找到到一条一条s-t 路路P,沿沿P对当前流进行增广对当前流进行增广,并重复并重复STEP3.STEP1.若若 1,结束结束,已经得到最优解已经得到最优解;否则进行下一步否则进行下一步.STEP2.构造构造 -残量网络残量网络 N(x，).STEP0.置初始可行流置初始可行流 x（如零流）（如零流）;=.STEP4.=/2；转；转STEP1.定定义义：对对N=(s,t,V,A,U)中中给给定定的的s-t可可行行流流x，网网络络N关关于于流流x的的 -残残量量网网络络N(x，)是是其其残残量量网网络络N(x)的的子子网网络络，它它由由残残留留容容量量不不小于小于 的弧组成的弧组成.整数容量网络，整数容量网络，N(x，1)=N(x).容容量量变变尺尺度度算算法法每每次次都都找找一一条条增增广广容容量量“充充分分大大”的的增增广广路路,但但不一定最大不一定最大.24容量变尺度算法算法 复杂性分析复杂性分析 的值总共有的值总共有O（logU）种取法）种取法.我们下面说明在给定的我们下面说明在给定的 下，最多执行下，最多执行2m次增广次增广：由由于于在在2-残残量量网网络络中中已已经经没没有有增增广广路路，因因此此在在-残残量量网网络络中中的的最最大大流流不不会会超超过过2m.因因为为-残残量量网网络络中中的增广路的容量至少为的增广路的容量至少为 ，因此增广次数不会超过，因此增广次数不会超过2m.算算法法总总的的增增广广次次数数是是O（m logU）次次，而而每每次次增增广广路路的的查查找找可可以以采采用用前前面面介介绍绍的的标标号号算算法法，即即复复杂杂度度为为O（m）.因此，算法总复杂度为因此，算法总复杂度为O（m2 logU）.仍不是强多项式时间算法仍不是强多项式时间算法25布 置 作 业（第第1 1讲）讲）目的掌握流网络的基本概念和基本性质；掌握几种典型的增广路算法及复杂性分析内容网络优化第网络优化第184-189页页3;4；5；（第；（第1讲）讲）思考1（1）-（7）；20（不交）（不交）26网网 络络 优优 化化 Network Optimizationhttp:/ 谢金星办公室：理科楼1308#（电话：62787812）Email: http:/ 6章章 最大流问题最大流问题 (Maximum Flow Problem)第第2讲讲27 -概论概论Ford-Fulkerson标号算法每次只是在所有增广路中随便地找一条进行增广标号算法每次只是在所有增广路中随便地找一条进行增广最大容量增广路算法每次都找一条增广容量最大的增广路进行增广最大容量增广路算法每次都找一条增广容量最大的增广路进行增广与与最最大大容容量量增增广广路路算算法法对对称称，一一个个自自然然的的想想法法是是:如如果果每每次次都都找找一一条条包包含含弧弧数数最最少少的的增增广广路路（称称为为最最短短增增广广路路）,则则算算法法效效果果如如何何？这这样样的的算算法法称称为为最最短增广路算法短增广路算法 本节主要结果之一本节主要结果之一：最短增广路算法最多经过：最短增广路算法最多经过O（mn）次增广后终止）次增广后终止.对对于于这这时时特特殊殊的的最最短短路路问问题题,我我们们可可以以很很容容易易构构造造最最短短路路算算法法在在O（m）的的时时间间内内找找到到一一条条最最短短增增广广路路(例例如如可可以以采采用用从从节节点点s或或t开开始始的的广广度度优优先先搜搜索索方方法法)，因此这种实现方法的复杂度为，因此这种实现方法的复杂度为O（m2n）.本本节节主主要要结结果果之之二二：在在O（n）的的时时间间内内找找到到一一条条最最短短增增广广路路，即即算算法法复复杂杂度度为为O（mn2）从从目目前前已已有有的的理理论论分分析析和和计计算算经经验验来来看看，最最短短增增广广路路算算法法是是所所有有增增广广路路算算法法中中效效果果最最好好的的算算法法，可可以以设设计计出出在在O（logn）的的平平均均时时间间内内找找到到一一条条最最短短增增广路，即算法复杂度为广路，即算法复杂度为O（mnlogn）6.3 6.3 最短增广路算法最短增广路算法28定定义义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），或或称称距距离离标标号号（函函数数）d 是是有有效的效的.如如果果任任意意一一个个节节点点的的距距离离标标号号正正好好等等于于残残量量网网络络中中从从该该节节点点到到汇汇点点（节节点点t t）的的所所有有有有向向路路中中弧弧数数最最少少的的有有向向路路所所包包含含的的弧弧数数(当当令令所所有有弧弧的的长长度度为为1 1时时,这这就就是是从从该该节节点点到到汇汇点点的的最最短短路路路路长长,因因此此我我们们后后面面直直接接称称为为最最短短路路路路长长)，则称距离函数，则称距离函数d d关于流关于流x x是是精确的精确的(exact)(exact)，或称距离标号是精确的，或称距离标号是精确的.如如果果对对N N（x x）中中的的某某一一条条弧弧（i i，j j）有有d（i）=d（j）+1+1，则则称称弧弧（i i，j j）为为允允许许弧弧(Admissible(Admissible Arc).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 st t精确的精确的 对于一个残量网络对于一个残量网络N（x），如何确定其精确的距离标号呢？），如何确定其精确的距离标号呢？从汇点（节点从汇点（节点t）开始，对）开始，对N（x）沿反向弧进行广度优先搜索）沿反向弧进行广度优先搜索这一过程的复杂度为这一过程的复杂度为O（m）.可可以以看看出出，一一个个节节点点的的精精确确的的距距离离标标号号实实际际上上表表示示的的是是从从该该节节点点到到汇汇点点（节节点点t）的的最最短短路路路路长长，也也就就是是说说对对所所有有节节点点按按照照最最短路路长进行了层次划分短路路长进行了层次划分.30距离标号距离标号 性质性质 引理引理6.3 若距离函数若距离函数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（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 在最短增广路算法中在最短增广路算法中,距离标号始终保持是有效的距离标号始终保持是有效的.归归纳纳法法：在在预预处处理理阶阶段段，构构造造的的距距离离标标号号是是有有效效的的.只只需需证证明明一次增广操作和一次重新标号操作不改变距离标号的有效性一次增广操作和一次重新标号操作不改变距离标号的有效性.增广操作可能引起残量网络的弧的变化只有两种情况：增广操作可能引起残量网络的弧的变化只有两种情况：允允许许路路上上的的弧弧(i，j)可可能能退退出出残残量量网网络络:这这不不会会影影响响(i，j)弧弧的的端端点点上上的的距距离标号的有效性；离标号的有效性；(j，i)弧弧可可能能进进入入残残量量网网络络:由由于于(i，j)弧弧是是允允许许弧弧，因因此此d(i)=d(j)+1，所所以以d(j)=d(i)-10:不会破坏任意的不会破坏任意的(i，j)弧的端点上的距离标号的有效性弧的端点上的距离标号的有效性;重重新新标标号号时时节节点点i在在残残量量网网络络中中没没有有允允许许弧弧,即即对对于于任任意意的的(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 用用最最短短增增广广路路算算法法计计算算如如下下网网络络图图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 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）:对对每每个个节节点点i，用用一一个个指指针针指指向向下下一一条条将将要要被被检检索索的弧，这条弧称为当前弧的弧，这条弧称为当前弧.算法开始时，当前弧为算法开始时，当前弧为A（i）中的第一条弧。）中的第一条弧。在在查查找找从从该该节节点点出出发发的的允允许许弧弧时时，总总是是从从当当前前弧弧开开始始判判别别：如如果果当当前前弧弧是是允允许弧，则返回这条弧；否则令许弧，则返回这条弧；否则令A（i）中的下一条弧为当前弧。）中的下一条弧为当前弧。如此下去，直到找到一条允许弧或判别完如此下去，直到找到一条允许弧或判别完 A（i）的最后一条弧为止。）的最后一条弧为止。6.3.3 复杂度分析 1 12 24 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)的两种情况：的两种情况：(1)uij(x)=0;(2)d(i)0的的节节点点i()称称为为活活跃跃的的(Active).42STEP1.STEP1.如如果果残残量量网网络络中中不不存存在在活活跃跃节节点点,结结束束,已已经经得得到到最最优优解解;否则继续否则继续.6.4.1 6.4.1 一般的预流推进算法一般的预流推进算法 正正确确性性：算算法法的的每每次次迭迭代代是是一一次次推推进进操操作作(STEP2的的前前面面部部分分)或或者者一一次次重重新新标号操作标号操作(STEP2的后面部分的后面部分).如如果果推推进进的的流流量量等等于于弧弧上上的的残残留留容容量量,则则称称为为饱饱和和推推进进(saturating push),否否则称为则称为非饱和推进非饱和推进(nonsaturating push).算法预处理阶段已经令距离标号算法预处理阶段已经令距离标号d（s）=n,网络中永远不会有增广路存在网络中永远不会有增广路存在.当当算算法法终终止止时时,网网络络中中不不含含有有活活跃跃节节点点,此此时时得得到到的的预预流流实实际际上上已已经经是是一一个个可行流可行流.因此是最大流。因此是最大流。STEP0.(预处理预处理)置置初初始始可可行行流流x为为零零流流;对对节节点点s的的每每条条出出弧弧（s，j）令令 ;对对任任意意的的 i V 计计算算精精确确的的距距离离标标号号d（i）；令令d（s）=n.STEP2.在在网网络络中中选选取取活活跃跃节节点点i；如如果果存存在在节节点点i的的某某条条出出弧弧(i,j)为为允允许许弧弧，则则将将 个个单单位位的的流流从从节节点点i推推进进到到节节点点j；否否则则令令d（i）=mind(j)+1|(i,j)A(x)且且 0.转转STEP1.436.4.1 6.4.1 一般的预流推进算法一般的预流推进算法例例6.8 6.8 用用预预流流推推进进算算法法计计算算如如下下图图6.86.8网网络络（a a）中中的的最最大大流流（弧上数字表示容量）（弧上数字表示容量）.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 32 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,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，j）的推进操作可能引起残量网络弧的变化只有两种情况：）的推进操作可能引起残量网络弧的变化只有两种情况：（i，j）弧可能退出残量网络（饱和推进），不影响距离标号的有效性；弧可能退出残量网络（饱和推进），不影响距离标号的有效性；（j，i）弧弧可可能能进进入入残残量量网网络络，由由于于(i，j)弧弧是是允允许许弧弧，因因此此 d(i)=d(j)+1，所以所以d（j）=d（i）-10.显然显然,这不会破坏任意的这不会破坏任意的(i，j)弧的端点上的距离标号的有效性弧的端点上的距离标号的有效性.由于重新标号时节点由于重新标号时节点i在残量网络中没有允许弧在残量网络中没有允许弧,也就是说对于任意的也就是说对于任意的(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都存在一条有向路都存在一条有向路.证明证明 对于任何一个预流对于任何一个预流 x 有有e(i)0,e(s)0(i s).根根据据流流的的分分解解定定理理,x在在原原网网络络N中中一一定定可可以以分分解解为为一一系系列列路路流流和和圈流之和圈流之和,并且这些路流总是从并且这些路流总是从s到到t或一个活跃节点或一个活跃节点.由由于于任任何何圈圈流流以以及及从从s到到t的的路路流流不不会会使使得得任任何何节节点点i(i s,t)产产生生赢赢余余,因因此此对对于活跃节点于活跃节点i,x在原网络在原网络N中分解的路流一定有一个是从中分解的路流一定有一个是从 s 到活跃节点到活跃节点i.于是于是,在残量网络中在残量网络中,一定有一条从一定有一条从i到节点到节点s的有向路的有向路.6.4.2 复杂度分析引引理理6.10 在在预预流流推推进进算算法法的的执执行行过过程程中中,d(i)2n.因因此此,修修改改距距离离标号的总次数不超过标号的总次数不超过2n2.证证明明 当当算算法法最最后后一一次次对对节节点