网络系统的最小费用最大流问题(课堂PPT).ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,网络中的最小费用最大流问题,二、基本概念与基本定理,三、寻求最大流的标号法,四、最小费用最大流问题,一、引言,1,2025/6/4 周三,2,网络系统的最大流问题,一,、,引言,在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。,2025/6/4 周三,3,网络系统的最大流问题,图,8.23,是一个网络,v,t,v,3,v,2,v,1,v,4,v,s,17,3,5,10,8,6,11,4,5,3,C,ij,每一个弧旁边的权就是对应的容量（即最大通过能力）。要求指定一个运输方案，使得从,v,s,到,v,t,的货运量最大，这是寻求网络系统的最大流问题,。,2025/6/4 周三,4,网络系统的最大流问题,二、基本概念与基本定理,定义,8.5,设一个赋权有向图,D,=,（,V,A,）,在,v,中指定一个,发点（或源点）,v,s,和一个,收点（或汇点）,v,t,其他的点叫做,中间点,。对于,D,中的每一个弧（,v,i,v,j,）,A,都有一个权,c,ij,叫做,弧的容量,。我们把这样的图,D,叫做一个,网络系统,，简称网络，记做,D,=,（,V,，,A,，,C,）。,网络,D,上的流,，是指定义在弧集合,A,上的一个函数,f,=,f,(,v,i,v,j,)=,f,ij,f,(,v,i,v,j,)=,f,ij,叫做弧在,(,v,i,v,j,),上的流量,。,2025/6/4 周三,5,网络系统的最大流问题,v,3,v,2,v,1,v,4,v,s,（,2,）,（,3,）,（,2,）,（,5,）,（,3,）,（,3,）,（,6,）,（,1,）,（,1,）,（,2,）,f,ij,图,8.,2,4,网络上的一个流（运输方案）,每一个弧上的流量,f,ij,就是运输量,例如,f,s1,=5,f,s2,=3,f,13,=2,等等,v,t,2025/6/4 周三,6,网络系统的最大流问题,网络系统上,流,的特点：,(1),发点的总流出量和收点的总流入量必相等；,(2),每一个中间点的流入量与流出量的代数和等于零；,(3),每一个弧上的流量不能超过它的最大通过能力（即容量）。,2025/6/4 周三,7,网络系统的最大流问题,定义,8.6,网络上的一个流,f,叫做,可行流,，如果,f,满足以下条件,（,1,）,容量限制条件,：对每一弧（,v,i,v,j,）,A,有,0,f,ij,c,ij,.,（,2,）,平衡条件,：,对于发点,v,s,，有,f,sj,-,f,js,=,v,(,f,),对于收点,v,t,，有,f,tj,-,f,jt,=-v(,f,),对于中间点，有,f,ij,-,f,ji,=0,式中,v,(,f,),叫做这个可行流的流量,，即,发点的净输出量（或收点的净输入量）,2025/6/4 周三,8,网络系统的最大流问题,任意一个网络上的,可行流总是存在,的。例如零流,v,(,f,)=0,就是满足以上条件的可行流。,网络系统中,最大流问题,就是在给定的网络上寻求一个可行流,f,使其流量,v,(,f,),达到最大值。,设流,f,=,f,ij,是网络,D,上的一个可行流，我们把,D,中,f,ij,=,c,ij,的弧叫做,饱和弧,，,f,ij,0,的弧为,非零流弧,，,f,ij,=0,的弧叫做,零流弧,。,2025/6/4 周三,9,网络系统的最大流问题,设,是网络,D,中连接发点,s,和收点,v,t,的一条,链,。定义链的方向是从,v,s,到,v,t,，于是链,上的弧被分为两类：一是弧的方向与链的方向相同，叫做,前向弧,，前向弧的集合记做,+,。二是弧的方向与链的方向相反，叫做,后向弧,，后向弧的集合记做,-,。,2025/6/4 周三,10,在下图（图,8.23,与,8.24,合并图）中，,(v,4,v,3,),是,饱和弧,，其他的弧是,非饱和弧,，并且都是,非零流弧,。,v,3,v,2,v,1,v,4,v,s,（,17,2,）,（,3,3,）,（,5,2,）,（,10,5,）,（,8,3,）,（,6,3,）,（,11,6,）,（,4,1,）,（,5,1,）,（,3,2,）,f,ij,如图，在链,（,v,s,v,1,v,2,v,3,v,4,v,t,),中，,+,=(,v,s,v,1,),(,v,1,v,2,),(,v,2,v,3,),(,v,4,v,t,),-,=(,v,4,v,3,).,v,t,网络系统的最大流问题,11,网络系统的最大流问题,增广链,，如果链,满足以下条件：,1,在弧（,v,i,v,j,）,+,上，有,0,f,ij,c,ij,即,+,中的每一条弧是,非饱和弧,。,2,在弧（,v,i,v,j,）,-,上，有,0,f,ij,c,ij,即,-,中的每一条弧是,非零流弧,。,例如在图,8.24,中，链,=,（,v,s,v,1,v,2,v,3,v,4,v,t,）就是一条增广链。,2025/6/4 周三,12,网络系统的最大流问题,定义,8.8,设一个网络,D,=,（,V,，,A,，,C,）。如果点集,V,被剖分为两个非空集合,V,1,和,V,1,，发点,v,s,V,1,收点,v,t,V,1,那么将弧集（,V,1,V,1,）叫做是,分离,v,s,和,v,t,的截集,。,定义,8.9,设一个截集（,V,1,V,1,），将截集（,V,1,V,1,）中所有的弧的,容量的和,叫做,截集的截量,，记做,c,(,V,1,V,1,),亦即,c,(,V,1,V,1,)=,c,ij ,(,v,i,v,j,)(,V,1,V,1,),设图,D,=(,V,，,A,，,C,),，点集,S,T,V,S,T,=,中，将起点在,S,，终点在,T,的所有弧构成的集合，记做（,S,，,T,）。,2025/6/4 周三,13,网络系统的最大流问题,下面的事实是显然的,：一个网络,D,中，任何一个可行流,f,的流量,v,(,f,),都小于或等于这个网络中任何一个截集,(,V,1,V,1,),的截量。并且，如果网络上的一个可行流,f*,和网络中的一个截集（,V,1,*,V,1,*,），满足条件,v,*,(,f,*,)=,c,(,V,1,*,V,1,*,),那么,f,*,一定是,D,上的最大流，而（,V,1,*,V,1,*,）一定是,D,的所有的截集中截量最小的一个（即最小截集）。,2025/6/4 周三,14,网络系统的最大流问题,定理,8.8,网络中的一个可行流,f*,是最大流的,充要条件,是不存在关于,f,*,的增广链。,定理,8.9,在一个网络,D,中，最大流的流量等于分离,v,s,和,v,t,的最小截集的截量。,定理,8.8,实际上提供了一个,寻求网络系统最大流的方法,：如果网络,D,中有一个可行流,f,，只要判断网络是否存在关于可行流,f,的增广链。如果没有增广链，那么,f,一定是最大流。如有增广链，那么可以按照定理,8.9,，不断改进和增大可行流,f,的流量，最终可以得到网络中的一个最大流。,2025/6/4 周三,15,网络系统的最大流问题,三、寻求最大流的,标号法,从网络中的一个可行流,f,出发（如果,D,中没有,f,，可以令,f,是零流），运用标号法，经过,标号过程,和,调整过程,，可以得到网络中的一个最大流。,用给顶点标号的方法来定义,V,1,*,.,在标号过程中，有标号的顶点是,V,1,*,中的点，没有标号的点不是,V,1,*,中的点。如果,v,t,有了标号，表示存在一条关于,f,的增广链。如果标号过程无法进行下去，并且,v,t,未被标号，则表示不存在关于,f,的增广链。这样，就得到了网络中的一个最大流和最小截集。,2025/6/4 周三,16,网络系统的最大流问题,1,标号过程,在标号过程中，网络中的点或者是,标号点,（,分为已检查和未检查两种,）或者是,未标号点,。每个标号点的标号包含两部分：第一个标号表示这个标号是从哪一点得到的，以便找出增广链。第二个标号是为了用来确定增广链上的调整量,。,标号过程开始,，先给,v,s,标号（,0,，,+,）。这时，,v,s,是标号而未检查的点，其他都是未标号点,。一般地，取一个标号未检查点,v,i,，对一切未标号点,v,j,：,2025/6/4 周三,17,网络系统的最大流问题,1),如果在弧（,v,i,v,j,）上，,f,ij,0,那么给,v,j,标号（,-,v,i,l,(,v,j,),）,其中,l,(v,j,)=min,l,(,v,i,),f,ji,.,这时，,v,j,成为标号未检查点。,(,考虑,后向弧,),于是,v,i,成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果,v,t,被标上号，表示得到一条增广链,，转入下一步调整过程。,2025/6/4 周三,18,2.,调整过程,首先按照,v,t,和其他点的第一个标号，利用,“,反向追踪,”,的办法，找出增广链,。例如，令,v,t,的第一个标号是,v,k,，则弧（,v,k,v,t,）在,上。再看,v,k,的第一个标号，若是,v,i,，则弧,(,v,i,v,k,),都在,上。依次类推，直到,v,s,为止。这时，所找出的弧就成为网络,D,的一条增广链,。取调整量,=,l,(,v,t,),即,v,t,的第二个标号，,网络系统的最大流问题,2025/6/4 周三,19,f,ij,+,，当,(,v,i,v,j,),+,令,f,ij,=,f,ij,-,，当,(,v,i,v,j,),-,f,ij ,当,(,v,i,v,j,)|,再去掉所有的标号，对新的可行流,f,=,f,ij,重新进行标号过程，直到找到网络,D,的最大流为止。,网络系统的最大流问题,2025/6/4 周三,20,网络系统的最大流问题,V,4,V,1,V,2,V,3,V,s,（,2,1,）,（,3,0,）,（,4,3,）,（,3,3,）,（,5,1,）,（,2,2,）,（,5,3,）,（,1,1,）,（,1,1,）,(,C,ij,f,ij,),V,t,图,8.21,2025/6/4 周三,21,例,8.8,求图,8.21,的网络最大流，弧旁的权数表示（,c,ij,f,ij,）。,解：用标号法。,1.,标号过程。,（,1,）首先给,v,s,标号（,0,，,+,）,（,2,）检查,v,s,:,在弧,(,v,s,v,2,),上,f,s2,=,c,s2,=3,不具备标号条件。在弧,(,v,s,v,1,),上,f,s1,=10,故给,v,2,标号（,-,v,1,l,(,v,2,),）,其中,l,(,v,2,)=min,l,(,v,1,),f,21,=min,4,1,=1.,网络系统的最大流问题,2025/6/4 周三,22,（,4,）检查,v,2,:,在弧（,v,2,v,4,）上，,f,24,=30,故给,v,3,标号（,-,v,2,，,l,(,v,3,),其中,l,(,v,3,)=min,l,(,v,2,),f,32,=min,1,1,=,1,。,（,5,）在,v,3,v,4,中任意选一个，比如,v,3,在弧（,v,3,v,t,）上，,f,3t,=1,c,3t,=2,故给,v,t,标号,(,v,3,l,(,v,t,),其中,l,(,v,t,)=min,l,(,v,3,),(,c,3t,-,f,3t,)=min,1,1,=1.,因为,v,t,被标上号，根据标号法，,转入调整过程,。,网络系统的最大流问题,2025/6/4 周三,23,2.调整过程。,从,v,t,开始，按照标号点的第一个标号，用,反向追踪,的方法，找出一条从,v,s,到,v,t,的增广链,=,v,s,v,1,v,2,v,3,v,t,，如,图8.22,中双箭线所示。,不难看出,+=(,v,s,v,1,),(,v,3,v,t,),-=(,v,2,v,1,),(,v,3,v,2,),取=,l,(,v,t,)=,1，在上调整f，得到,在+上，,f,s1,+=1+1=2,在+上，,f,3t,+=1+1=2,在-上，,f,21,-=1-1=0,在-上,，,f,32,-=1-1=0,其他的,f,ij,不变,。,网络系统的最大流问题,2025/6/4 周三,24,网络系统的最大流问题,V,4,V,1,V,2,V,3,V,s,（,2,1,）,（,3,0,）,（,4,3,）,（,3,3,）,（,5,1,）,（,2,2,）,（,5,3,）,（,1,1,）,（,1,1,）,(,C,ij,f,ij,),V,t,(,v,2,1),(,0,，,+,),(-,v,1,1),(,v,s,4),(-V,2,1),图,8.22,2025/6/4 周三,25,调整后的可行流,f,*,，如图,8.23,所示，再对这个可行流重新进行标号过程，寻找增广链：,首先给,v,s,标号（,0,，,+,），检查,v,s,给,v,1,标号（,v,s,3,）。检查,v,1,在弧（,v,1,v,3,）上，,f,1,3,=,c,13,弧（,v,2,v,1,）上，,f,21,=0,均不符合标号过程,(1),的条件。因此标号过程无法进行下去，不存在从,V,S,到,V,t,的增广链，算法结束。,这时，网络中的可行流,f,*,即是最大流，最大流的流量,V,(,f,*,)=,f,s1,+,f,s2,=5.,同时，也找出,D,的最小截集（,V,1,，,V,1,），其中,V,1,是标号的集合，,V,1,是未标号的集合。,网络系统的最大流问题,2025/6/4 周三,26,网络系统的最大流问题,V,4,V,1,V,2,V,3,V,s,（,2,1,）,（,3,0,）,（,4,3,）,（,3,3,）,（,5,2,）,（,2,2,）,（,5,3,）,（,1,0,）,V,t,(,0,，,+,),(,v,s,3),图,8.23,(,C,ij,f,ij,),（,1,0,）,2025/6/4 周三,27,四、最小费用最大流问题,在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。,网络系统的最小费用最大流问题,2025/6/4 周三,28,设一个网络,D,=,（,V,，,A,，,C,）,，对于每一个弧,(,v,i,v,j,),A,给定一个单位流量的费用,b,ij,0,，网络系统的,最小费用最大流问题,，是指要寻求一个最大流,f,，使流的总费用,b,(,f,)=,b,ij,f,ij,达到最小。,（,V,i,V,j,）,A,网络系统的最小费用最大流问题,2025/6/4 周三,29,在一个网络,D,中，当沿可行流,f,的一条增广链,，以调整量,=1,改进,f,，得到的新可行流,f,的流量，有,v,(,f,)=,v,(,f,)+1,，而此时总费用,b,(,f,),比,b,(,f,),增加了,b,(,f,)-,b,(,f,)=,b,ij,(,f,ij,-f,ij,)-,b,ij,(,f,ij,-f,ij,)=,b,ij,-,b,ij,+,-,+,-,将,b,ij,-,b,ij,叫做这条,增广链的费用,。,+,-,网络系统的最小费用最大流问题,2025/6/4 周三,30,网络系统的最小费用最大流问题,如果可行流在流量为,v,(,f,),的所有可行流中的费用最小，并且是,关于,f,的所有增广链中的费用最小的增广链，那么沿增广链,调整可行流,f,，得到的新可行流,f,，也是流量为,v,(,f,),的所有可行流中的最小费用流。,依次类推，当,f,是最大流时，就是所要求的最小费用最大流。,2025/6/4 周三,31,显然，零流,f,=0,是流量为,0,的最小费用流。一般地，寻求最小费用流，总可以从零流,f,=0,开始。下面的问题是：如果已知,f,是流量为,v,(,f,),的最小费用流，那么就要去,寻找关于,f,的最小费用增广链,。,对此，重新构造一个赋权有向图,W,(,f,),，其顶点是原网络,D,的顶点，而将,D,中的每一条弧,(,v,i,v,j,),变成两个相反方向的弧（,v,i,v,j,）和,(,v,j,v,i,),，并且定义,W,(,f,),中弧的权,w,ij,为：,网络系统的最小费用最大流问题,2025/6/4 周三,32,b,ij,当,f,ij,0,w,ji,=,+,当,f,ij,=0,(,将权为,+,的弧从,W(f),中略去,),即当,0,f,ij,c,ij,时，成为,2,条方向相反，权绝对值相等的弧。否则不变。,网络系统的最小费用最大流问题,2025/6/4 周三,33,这样，在网络,D,中寻找关于,f,的,最小费用增广链,就等于价于在,W(f),中,寻求从,v,s,到,v,t,的最短路,。算法如下：,算法开始，取零流,f,(0),=0.,一般地，如果在第,K,-1,步得到最小费用流,f,(K-1),则构造图,W,（,f,(K-1),）。在图,W,（,f,(K-1),）中，寻求从,v,s,到,v,t,的最短路。如果不存在最短路,(,即最短路权是,+,),，则,f,(K-1),就是最小费用最大流。如果存在最短路，则在原网络,D,中得到相对应（一一对应）的增广链,，,在增广链,上对,f,(K-1),进行调整，取调整量,=minmin(,c,ij,-f,(k-1),ij,),min(,f,(k-1),ij,).,+,-,网络系统的最小费用最大流问题,2025/6/4 周三,34,令,f,(k-1),ij,+,，,当,(,v,i,v,j,),+,f,(k),ij,=,f,(k-1),ij,-,，,当,(,v,i,v,j,),-,f,(k-1),ij,，当,(,v,i,v,j,)|,得到一个新的可行流,f,(k),，在对,f,(k),重复以上的步骤，直到,D,中找不到相对应的增广链时为止。,网络系统的最小费用最大流问题,2025/6/4 周三,35,例,8.9,求图,8-24,所示网络中的最小费用最大流，弧旁的权是（,b,ij,c,ij,）,.,网络系统的最小费用最大流问题,(,b,ij,C,ij,),(1,8),v,t,v,3,v,2,v,s,v,1,(3,10),(2,4),(6,2),(1,7),(4,10),(2,5),2025/6/4 周三,36,解：,（,1,）取初始可行流为零流,f,(0),=0,构造赋权有向图,W(f,(0),),求出从,v,s,到,v,t,的最短路,(,v,s,v,2,v,1,v,t,),如图,8.25a,中双箭头所示即为最短路。,网络系统的最小费用最大流问题,(1),V,t,V,3,V,2,V,s,V,1,(3),(2),(6),(1),(4),(2),W(f,(0),),图,8.25a,2025/6/4 周三,37,（,2,）在原网络,D,中，与这条最短路相对应的增广链为,=,（,v,s,v,2,v,1,v,t,）。,（,3,）在,上对,f,(0),=0,进行调整，取,=5,，得到新可行流,f,(1),。类似地，按照以上的算法，依次类推，可以得到,f,(1),，,f,(2),，,f,(3),，,f,(4),，,流量分别为,5,，,7,，,10,，,11,，并且分别构造相对应的赋权有向图,W(f,(1),),W,(,f,(2),),W,(,f,(3),),W,(,f,(4),),。,由于在,W(f,(4),),中已经不存在从,v,s,到,v,t,的最短路，因此，可行流,f,(4),，,v(f,(1),),=11,是最小费用最大流。,网络系统的最小费用最大流问题,2025/6/4 周三,v,s,v,t,v,2,v,3,v,1,(10,4,),(7,1,),(8,1,),(10,3,),(4,2,),(5,2,),(2,6,),(5,2,5,),(7,1,5,),v,s,v,t,v,2,v,3,v,1,(10,4,0),(8,1,5,),(10,3,0),(4,2,0),(2,6,0),第,1,次 迭 代,原图全部是零流弧,保持原边不变,单位费用为权；,所有的权均大于零，,构造赋权有向图并,求出最短路：,恰也是,最小费用增广链,。,流量调整量,1,=min8-0,5-0,7-0=5,总流量,f,1,=5,最小费用增广链的费用,b,ij,=1+2+1=4,总费用,C,1,=45=20,(,容量费用图,(,c,ij,b,ij,),第,2,次 迭 代,(,3,1,),v,1,v,t,(5,-2,),(2,6,),v,2,v,3,(10,4,),(,5,-1,),(10,3,),(4,2,),（,2,1,）,v,s,（,5,，,-1,）,(7,1,7,),v,s,v,t,v,2,v,3,v,1,(10,4,2,),(8,1,5),(10,3,0),(4,2,0),(2,6,0),(5,2,5),零流弧保持原边,非饱和弧和非零流弧,(v,s,v,2,),和,(v,1,v,t,),增添反向弧,将饱和弧,(v,2,v,1,),变成反向弧；,继续,构造赋权有向图并,求出最短路,:,恰也是最小费用增广链,。,流量调整量,2,=min10-0,7-5=2,，,总流量,=,原流量,+,新增流量,=5+2=7,；,最小费用增广链的费用,b,ij,=4+1=5,总费用,C,2,=,原费用,+,新增费用,=20+52=30,v,s,v,t,v,2,v,3,v,1,(8,4,),（,2,-4,）,(5,-1,),(7,-1,),(10,3,),(4,2,),(2,6,),(5,-2,),(3,1,),零流弧保持原边，此外的非饱和弧增添反向弧，饱和弧去掉原边增添反向虚线弧，变成反向弧,继续,构造赋权有向图并,求出最短路,:,恰也是最小费用增广链。,流量调整量,3,=min8-5,10-0,4-0=3,，,总流量,=,原流量,+,新增流量,=7+3=10,；,最小费用增广链的费用,b,ij,=1+3+2=6,总费用,C,3,=,原费用,+,新增费用,=30+63=48,第,3,次 迭 代,(7,1,7),v,s,v,t,v,2,v,3,v,1,(10,4,2),(8,1,8,),(10,3,3,),(4,2,3,),(2,6,0),(5,2,5),(2,6,),(7,3,),(8,4,),v,s,v,t,v,2,v,3,v,1,(3,-3,),(7,-1,),(8,-1,),(3,-2,),（,1,2,）,(2,-4,),（,5,-2,）,零流弧保持原边，此外的非饱和弧增添反向弧，饱和弧去掉原边增添反向虚线弧，变成反向弧；,继续,构造赋权有向图并,求出最短路,:,对应的最小费用增广链是,流量调整量,4,=min10-2,5,10-3,4-3=1,，,总流量,=,原流量,+,新增流量,=10+1=11,；,最小费用增广链的费用,b,ij,=4-2+3+2=7,总费用,C,4,=,原费用,+,新增费用,=48+71=55,。,由于总流量,11,已达到最大流量，故停止迭代，,当前的可行流图即最大流图。,第,4,次 迭 代,(7,1,7),v,s,v,t,v,2,v,3,v,1,(10,4,3,),(8,1,8),(10,3,4,),(4,2,4,),(2,6,0),(5,2,4,),例题总结：,1,、将饱和弧反向；,2,、将非饱和非零流弧加一反向弧；,3,、零流弧不变；,4,、所有正向弧的权为该弧的费用，反向弧的权为该弧费用的相反数。,42,2025/6/4 周三,求最小费用,-,最大流问题,求下图中网络从 到 的最小费用最大流，图中弧上的数字为 。,v,s,v,2,v,3,v,4,v,5,v,t,练习作业,43,2025/6/4 周三,v,s,v,2,v,3,v,4,v,5,v,t,(0),求网络的最大流量,由前面计算知，。将,0,流作为初始可行流。,扩展费用网络与原网络相同,(1),第一次迭代：,用,Ford,算法求最短增广链，路线是,v,s,v,3,v,5,v,t,44,2025/6/4 周三,v,s,v,2,v,3,v,4,v,5,v,t,调整流量：在增广链上有：,在初始可行流的基础上调整流量,得到新的可行流，刷新网络图,45,2025/6/4 周三,(2),第二次迭代,扩展费用网络,v,s,v,2,v,3,v,4,v,5,v,t,饱和弧,只能减小流量，单位费用减少,3,（,1,）流量还可增加,3,，单位费用,6,；（,2,）流量也可减小，当前流量为,6,，每减单位流量，费用节省,6,。,（,1,）流量还可增加,4,，单位费用,1,；（,2,）流量也可减小，当前流量为,6,，每减单位流量，费用节省,1,。,46,2025/6/4 周三,用,Ford,算法求最短增广链，路线是,v,s,v,2,v,5,v,t,v,s,v,2,v,3,v,4,v,5,v,t,在原可行流基础上调整流量,得到新的可行流，刷新网络图,47,2025/6/4 周三,(3),第三次迭代,扩展费用网络,v,s,v,2,v,3,v,4,v,5,v,t,用,Ford,算法求最短增广链，路线是,v,s,v,2,v,4,v,t,48,2025/6/4 周三,调整流量：在增广链上有：,在初始可行流的基础上调整流量,得到新的可行流，刷新网络图,v,s,v,2,v,3,v,4,v,5,v,t,49,2025/6/4 周三,(3),第四次迭代,扩展费用网络,用,Ford,算法求最短增广链，路线是,v,s,v,3,v,4,v,t,v,s,v,2,v,3,v,4,v,5,v,t,50,2025/6/4 周三,v,s,v,2,v,3,v,4,v,5,v,t,调整流量：在增广链上有：,在初始可行流的基础上调整流量,得到新的可行流，刷新网络图,51,2025/6/4 周三,