图论最大流问题.ppt

《图论最大流问题.ppt》由会员分享，可在线阅读，更多相关《图论最大流问题.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、网络与网络流网络与网络流一、网络流的基本概念一、网络流的基本概念先来看一个实例。先来看一个实例。现在现在想将一些物资从想将一些物资从S运抵运抵T，必须经过一些中转，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运站。连接中转站的是公路，每条公路都有最大运载量。载量。S、T和中转站作为点，每条公路作为弧作有向图，和中转站作为点，每条公路作为弧作有向图，每条弧上赋予该公路的最大运载量。最多能将多每条弧上赋予该公路的最大运载量。最多能将多少货物从少货物从S运抵运抵T？定义定义1若有向图满足下列条件：若有向图满足下列条件：(1)有且仅有一个入度为零的顶点有且仅有一个入度为零的顶点s，称为源点

2、；，称为源点；(2)有且仅有一个出度为零的顶点有且仅有一个出度为零的顶点t，称为汇点，称为汇点;(3)每一条弧每一条弧(vi,vj)都有一个非负数都有一个非负数cij，称为该，称为该边的容量。如果边的容量。如果vi,vj之间没有边，之间没有边，cij=0。则称之为网络，记为则称之为网络，记为N=(V,E,C).图图1所给出的一个赋权有向图所给出的一个赋权有向图N就是一个网络，就是一个网络，指定指定v1是源点，是源点，v4为汇点，弧旁的数字为为汇点，弧旁的数字为cij。图图1图图2网络流：是定义在弧集合网络流：是定义在弧集合E上一个函数上一个函数f=f(vi,vj)，并称，并称f(vi,vj)为

3、弧为弧(vi,vj)上的流量上的流量(简记为简记为fij)。如。如图图2所示的网络所示的网络N，弧上两个数，第一个数表示容量，弧上两个数，第一个数表示容量cij，第二个数表示流量，第二个数表示流量fij。二、可行流与最大流二、可行流与最大流1.定义定义在实际问题中，对于流有两个显然的要求：一是在实际问题中，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力每个弧上的流量不能超过该弧的最大通过能力(即弧即弧的容量的容量)；二是中间点的流量为；二是中间点的流量为0，源点的净流出，源点的净流出量量和汇点的净流入量必相等。因此有定义如下。和汇点的净流入量必相等。因此有定义如下。定义定

4、义2网络网络N中每条边都给定一个非负实数中每条边都给定一个非负实数fij满足满足下列条件下列条件(1)容量约束：容量约束：0fijcij，(vi,vj)E，(2)守恒条件守恒条件对于中间点：流入量对于中间点：流入量=流出量，即流出量，即对于源点与汇对于源点与汇点：源点的净流出量点：源点的净流出量=汇点的净汇点的净流入量，即流入量，即这一这一组组fij称为网络称为网络N上的上的可行流可行流,记为记为f，w称为流量称为流量.网络网络N中流值最大的流中流值最大的流f*称为称为N的的最大流最大流.2.可增广（流）路径可增广（流）路径可增广路径可增广路径，是指这条路径上的流可以修改，通，是指这条路径上的

5、流可以修改，通过修改，使得整个网络的流值增大。过修改，使得整个网络的流值增大。定义定义3设设f是一个可行流，是一个可行流，P是从源点是从源点s到汇点到汇点t的一的一条路，若条路，若P满足下列条件：满足下列条件：(1)在在P上的所有前向弧上的所有前向弧(vivj)都是非饱和弧，即都是非饱和弧，即0fijcij；(2)在在P上的所有后向弧上的所有后向弧(vivj)都是非零弧，即都是非零弧，即0fijcij。则称。则称P为为(关于可行流关于可行流f的的)一条可增广路一条可增广路径。径。3.割及其容量割及其容量定义定义4如果如果S是是V的一个子集，的一个子集，则称边集，则称边集为网络为网络N的一个的一

6、个割。显然，若把某一割的弧从网络中去掉，则割。显然，若把某一割的弧从网络中去掉，则从从s到到t就不存在路。所以直观上讲，割是从就不存在路。所以直观上讲，割是从s到到t的必经之道。的必经之道。定义定义5给一割给一割，把其中所有弧的容量，把其中所有弧的容量之和称为这个之和称为这个割的容量割的容量，记为，记为，即，即网络网络N中容量最小的割中容量最小的割称为称为N的的最小割最小割。不难证明，任何一个可行流的流量不难证明，任何一个可行流的流量w都不会超过都不会超过任一割的容量，即任一割的容量，即例如，图例如，图2中，若中，若图图2定理定理1网络的最大流量不超过最小的割的容量，即网络的最大流量不超过最小

7、的割的容量，即证明证明设设f是给定网络的任意可行流，由可行流的性质是给定网络的任意可行流，由可行流的性质任给一个割任给一个割即即所以所以因因由于由于所以所以由于可行流和割的任意性，定理成立。由于可行流和割的任意性，定理成立。如果网络的可行流不是最大流，就一定存在从如果网络的可行流不是最大流，就一定存在从s到到t的的可增流路径可增流路径。令令s,v1,v2,vk,t是一条是一条s到到t的路径的路径Pst，其中，其中每条边的方向都是每条边的方向都是vj到到vj+1,称为称为向前边向前边。如果这。如果这条路径上每条边条路径上每条边eij都有都有fijcij，那么令，那么令令令Pst每条边的流都增加每

8、条边的流都增加d d，所得流分布仍然是网，所得流分布仍然是网络的可行流分布，但流增加了络的可行流分布，但流增加了d d.(5,3)(2,1)(6,2)(4,1)(5,2)sv4tv1v2v3(5,4)(2,2)(6,2)(4,2)(5,3)sv4tv1v2v3d d=1图图3网络中网络中的一部分的一部分图图4还可以包含向后的可增流路径还可以包含向后的可增流路径Pst，要求向前边，要求向前边eij都有都有fij0,对前向边对前向边eij后向边后向边eji,图图5，d d=1,图图5，d d=1,(5,3)(2,1)(6,2)(4,1)(5,2)sv4tv1v2v3图图5，d d=1,(5,4)(

9、2,2)(6,1)(4,2)(5,3)sv4tv1v2v3(1,0)(2,0)(1,0)(2,0)(2,0)stacb第第1条可增路条可增路s,c,b,t,d(1,0)(1,0)(2,2)(1,0)(2,2)(2,2)stacbd(1,0)d d=2第第2条可增路条可增路s,a,b,c,d,t,(1,0)(1,0)(1,1)(2,2)(1,1)(2,1)(2,2)stacbd(1,1)(1,1)最大流最大流w=3图图6图图7图图8定理定理2最大流最小割定理：在一个网络最大流最小割定理：在一个网络N中，最中，最大流量等于最小割的容量大流量等于最小割的容量。证明证明设网络的一个可行流设网络的一个可

10、行流f 为最大流，确定一为最大流，确定一个割如下：个割如下：是向前边且是向前边且，则，则若若是后前边且是后前边且，则，则若若则则，否则存在否则存在s到到t的一条可增路，矛盾。的一条可增路，矛盾。因此，因此，则任意则任意的边的边(x,y)有有若若是向前边，是向前边，是后前边，是后前边，由定理由定理1，又又所以所以最大网络流最大网络流最大流问题实际上是求一可行流最大流问题实际上是求一可行流fij，使得，使得w达到最大。若给了一个可行流达到最大。若给了一个可行流f，只要判断，只要判断N中有中有无关于无关于f的的增广路径增广路径，如果有增广路径，改进，如果有增广路径，改进f，得到一个流量增大的新的可行

11、流；如果没有增广得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。路径，则得到最大流。设设是最小割，下面用是最小割，下面用顶点标号法顶点标号法来定义来定义S*，在标号过程中，有标号的顶点表示是，在标号过程中，有标号的顶点表示是S*中的中的点，没有标号的点表示不是点，没有标号的点表示不是S*中的点。中的点。如如果果t有有标号，则说明找到了一条增广路；标号，则说明找到了一条增广路；如果标号过程如果标号过程进行不下去，而进行不下去，而t没有标号，则说明不存在增广路，没有标号，则说明不存在增广路，于是得到了最大流，同时也得到了一个最小割集。于是得到了最大流，同时也得到了一个最小割集。求最大

12、流的标号法求最大流的标号法(Ford,Fulkerson)从一个可行流从一个可行流(一般取零流一般取零流)开始，不断进行以开始，不断进行以下的下的标号过程标号过程与与增广过程增广过程，直到找不到关于，直到找不到关于f的可的可增广路径为止。增广路径为止。1.标号过程标号过程A标记过程中每个结点给予标记过程中每个结点给予3个标号，第一个标号个标号，第一个标号表示该点的先驱点，第二个标号为表示该点的先驱点，第二个标号为“+”或或“-”，表示先驱点与该点连接的边在可增广路中是前，表示先驱点与该点连接的边在可增广路中是前向边还是反向边，第三个标号表示这条边上能增向边还是反向边，第三个标号表示这条边上能增

13、加或减少的流值。加或减少的流值。stepA1发点发点s标记为标记为(s，+,)，此时成为已标记，此时成为已标记，未检查，其余点均称为未标记，未检查。未检查，其余点均称为未标记，未检查。stepA2任选一已标记未检查的结点任选一已标记未检查的结点x，若结点，若结点y与与x邻接且未标记，则当邻接且未标记，则当(1)若若(x,y)E且且cxyfxy时，则时，则y标记为标记为(x,+,d dy)，其中，其中d dy=mind dx,cxy-fxy之后，称之后，称y已标记未检查。已标记未检查。(2)若若(y,x)E且且fyx0时，则时，则y标记为标记为(x,-,d dy)，其中其中d dy=mind d

14、x,fxy之后，称之后，称y已标记未检查。已标记未检查。(3)与结点与结点x邻接的所有结点都标记完之后，将邻接的所有结点都标记完之后，将x的的标记的符号标记的符号“+”或或“-”加以标记，表示加以标记，表示x已标记已标记且已检查。且已检查。StepA3重重复复stepA2，直直到到收收点点t被被标标记记，或或者者收收点点不不能能获获得得标标记记为为止止。如如果果是是前前者者，转转向向增增广广过过程程，如果是后者，算法结束，所得流即是最大流。如果是后者，算法结束，所得流即是最大流。2.增广过程增广过程BstepB1令令z=tstepB2若若z的标记为的标记为(q,+,d dz)，则，则若若z的标

15、记为的标记为(q,-,d dz)，则，则stepB3若若 q=s，则把全部标记去掉，则把全部标记去掉，转向标记转向标记过程过程A,否则令否则令z=q，转到，转到B2.例例求图求图9所示的最大流。边上的数字表示容量。所示的最大流。边上的数字表示容量。st8v1v4v3v2752961059设设f是任意可行流，从是任意可行流，从零流开始，设每条边零流开始，设每条边的流均为的流均为0，即，即1.找一条可增广路并增加其流值找一条可增广路并增加其流值A(标记过程标记过程)(1)发点发点s标记为标记为(s，+,)(2)考察与考察与s邻接的点邻接的点v1和和v2。对点。对点v1，则则图图9st8,0v1v4

16、v3v27,05,02,09,06,010,05,09,0于是，于是，v1标记为（标记为（s,+,8）同样的方法同样的方法v2得到标记（得到标记（s,+,7）。）。与与s邻接的点都已标记，邻接的点都已标记，s标记中的标记中的“+”写成写成，表示表示s已标记，已检查，如图已标记，已检查，如图10。图图10(s,)（s,+,8）（s,+,7）(3)重复重复stepA2,选一已标记、未检查的点，如选选一已标记、未检查的点，如选v1点，与点，与v1邻接且未标记的点只有邻接且未标记的点只有v3。因。因v3标记为标记为(v1,+,8)。点点v1已标记、已检查，将其标记中的已标记、已检查，将其标记中的“+”

17、写成写成，如图，如图11。st8,0v1v4v3v27,05,02,09,06,010,05,09,0图图11(s,)（s,8）（s,+,7）则则（v1,+,8）(4)重复重复stepA2,选一已标记、未检查的点，如选选一已标记、未检查的点，如选v3点，与点，与v3邻接且未标记的点有邻接且未标记的点有v4和和t。对于点对于点v4，因（，因（v4,v3）E 且且fv4v3=0，因此，不，因此，不能用点能用点v3去标记点去标记点v4.对于点对于点t，因，因st8,0v1v4v3v27,05,02,09,06,010,05,09,0图图12(s,)（s,8）（s,+,7）（v1,+,8）t标记为标记

18、为(v3,+,5)。如图如图12。由于由于t已标记，已标记，转到增广过程转到增广过程B.（v3,+,5）B.增广过程增广过程st8,5v1v4v3v27,05,02,09,06,010,05,59,5图图13至此，完成增广过程至此，完成增广过程。如图如图13。2.找一条可增广路并增加其流值找一条可增广路并增加其流值图图14A(标记过程标记过程)(2)考察与考察与s邻接的点邻接的点v1和和v2。对点。对点v1，st8,5v1v4v3v27,05,02,09,06,010,05,59,5(1)发点发点s标记为标记为(s，+,)(s,+,)st8,5v1v4v3v27,05,02,09,06,010

19、,05,59,5于是，于是，v1标记为（标记为（s,+,3）同样的方法同样的方法v2得到标记（得到标记（s,+,7）。）。与与s邻接的点都已标记，邻接的点都已标记，s标记中的标记中的“+”写成写成，表示表示s已标记，已检查，如图已标记，已检查，如图15。图图15(s,)（s,+,3）（s,+,7）(3)重复重复stepA2,选一已标记、未检查的点，如选选一已标记、未检查的点，如选v2点，与点，与v2邻接且未标记的点有邻接且未标记的点有v3,v4。因。因v4标记为标记为(v2,+,7)。v3不能同过不能同过v2标记。标记。点点v2已标记、已检查，将其标记中的已标记、已检查，将其标记中的“+”写成

20、写成，如图，如图16。st8,5v1v4v3v27,05,02,09,06,010,05,59,5图图16(s,)（s,3）（s,+,7）则则（v2,+,7）图图17st8,5v1v4v3v27,05,02,09,06,010,05,59,5(s,)（s,+,3）（s,7）（v2,7）（v4,+,7）图图18B.增广过程。从标记过程得到一条可增广路：增广过程。从标记过程得到一条可增广路：st8,5v1v4v3v27,75,02,09,76,010,75,59,5增值增值d d=7,于是得到图于是得到图18，至此又完成一次增广过程。，至此又完成一次增广过程。3.找一条可增广路并增加其流值找一条可

21、增广路并增加其流值图图19对图对图18重新标记得到图重新标记得到图19，得到一条可增广路：，得到一条可增广路：st8,5v1v4v3v27,75,02,09,76,010,75,59,5(s,)（s,+,3）（v1,3）（v2,+,2）（v4,+,2）增值增值d d=2,于是得到图于是得到图20。图图20st8,7v1v4v3v27,75,02,09,96,010,95,59,5图图214.对图对图20重新标记得到图重新标记得到图21，v4和和t均不能再获标均不能再获标记，算法结束。最大流为记，算法结束。最大流为14。st8,7v1v4v3v27,75,22,09,96,010,95,59,5

22、(s,)（s,1）（v1,1）（v1,1）将获得标记的结点归为将获得标记的结点归为S,不能标记的结点归为不能标记的结点归为即即图图22st8,7v1v4v3v27,75,22,09,96,010,95,59,5(s,)（s,1）（v1,1）（v1,1）得到最小割为：得到最小割为：其容量为其容量为可行流：可行流：网络网络N中每条边都给定一个非负实数中每条边都给定一个非负实数fij满满足下列条件足下列条件(1)容量约束：容量约束：0fijcij，(vi,vj)E，(2)守恒条件：对于中间点：流入量守恒条件：对于中间点：流入量=流出量，即流出量，即这一这一组组fij称为网络称为网络N上的上的可行流可

23、行流,记为记为f.网络网络N中对应上述可行流的流量：中对应上述可行流的流量：网络定义推广：入度为网络定义推广：入度为0和出度为和出度为0的限制去掉。的限制去掉。考虑推广后的网络。考虑推广后的网络。网络网络N中每条边都给定一个非负实数中每条边都给定一个非负实数fij满足下列满足下列条件条件(1)容量约束：容量约束：bijfijcij，(vi,vj)E，(2)守恒条件：对于中间点：流入量守恒条件：对于中间点：流入量=流出量，即流出量，即二二下界非零网络最大流算法下界非零网络最大流算法这一这一组组fij称为称为N上的上的可行流可行流,记为记为f，也称为流函数也称为流函数.求使流量求使流量最大的流函数

24、最大的流函数f.记记N为为N(V,E,s,t,b,c).下界非零的网络，流函数可能不存在。下界非零的网络，流函数可能不存在。sv2v1t5,61,23,47,8如图，边上的两个数分别为如图，边上的两个数分别为bij和和cij，其流函数不存在。，其流函数不存在。建立建立N(V,E,s,t,b,c)的的可行流可行流存在的充分必要条件。存在的充分必要条件。为了叙述方便引入记号：为了叙述方便引入记号：a a(v)和和b b(v)，分别表示进，分别表示进入入v和从和从v出来的边集合。出来的边集合。构造构造N(V,E,s,t,b,c)的伴随网络的伴随网络N1(V1,E1,s1,t1,b1,c1)：(1)V

25、1=Vs1,t1,s1,t1 V;(2)任何任何v V,加新边加新边e=vt1,且令且令c1(e)是是N1中边中边e的容量，下界的容量，下界b(e)=0.(3)任何任何v V,加新边加新边e=s1v,且令且令c1(e)是是N1中边中边e的容量，下界的容量，下界b(e)=0.(4)E中的边中的边e仍在仍在N1中保留，但中保留，但b1(e)=0,c1(e)=c(e)-b(e).(5)加新边加新边st与与ts的容量：下界均为的容量：下界均为0，容量为，容量为。定理定理N(V,E,s,t,b,c)存在可行流当且仅当伴随网存在可行流当且仅当伴随网络络N1(V1,E1,s1,t1,b1,c1)上的最大流上

26、的最大流f1使流出使流出s1的的一切边一切边e均满足均满足f1(e)=c1(e).这时这时f1(e)+b(e)是是N上上一个可行流。一个可行流。证明证明N1上的最大流上的最大流f1使流出使流出s1的一切边的一切边e均满足均满足f1(e)=c1(e).对于网络对于网络N，令，令 f(e)=f1(e)+b(e),e E则则f是是N上一个可行流上一个可行流.这是因为这是因为e E时时，即即f(e)满足约束条件满足约束条件(1).下面证明满足守恒条件下面证明满足守恒条件(2):对于对于v V-s,t,记记s s=s1v,t t=vt1,由于由于f1是是N1的的流函数，流函数，f1应满足应满足N1中的守

27、恒条件：中的守恒条件：又已知从又已知从s1出发的边出发的边e，f1(e)=c1(e),故故进入进入t1的边的边e，f1(e)=c1(e),故故即即f在在N中满足守恒条件中满足守恒条件(2).f是可行流是可行流.反之，若反之，若f是可行流，令是可行流，令f1是是N1中使流出中使流出s1的一切边的一切边e均满足均满足f1(e)=c1(e)的的最大流最大流.根据上述定理给出求下界非根据上述定理给出求下界非0的网络最大流的步骤：的网络最大流的步骤：(1)画出画出N的伴随网络的伴随网络N1。(2)求出求出N1的最大流的最大流f1。(3)检验检验f1是否使流出是否使流出s1的一切边的一切边e均满足均满足f

28、1(e)=c1(e).(4)若是，则若是，则N上有可行流上有可行流f,(5)f(e)=f1(e)+b(e)；(6)否则，否则，N上没有可行流。上没有可行流。(7)(4)若已得可行流若已得可行流f,将将f 放大，求放大，求N的最大流，这的最大流，这时时(8)无需考虑下界条件。无需考虑下界条件。sv1v30,101,33,52,6v2v45,7t2,8sv1v30,101,33,52,6v2v45,7t2,82,41,3sv1v310,2,4,v2v42,t6,t1s12,1,12,25,55,53,35,54,44,41,12,22,2,sv1v310,22,22,04,0v2v42,0t6,2

29、t1s12,02,11,12,25,55,53,35,54,44,41,12,28,58,0sv1v310,22,22,04,0v2v42,0t6,22,02,1sv1v310,23,35,36,2v2v47,5t8,44,23,2sv1v30,101,33,52,6v2v45,7t2,8第一个数字是第一个数字是c(e),第二个第二个是是f(e)=f1(e)+b(e)第一个数字是第一个数字是c1(e),第二个是第二个是f1(e)第一个数字是第一个数字是b(e),第二个是第二个是c(e)sv1v310,23,35,36,2v2v47,5t8,44,23,2第一个数字是第一个数字是c(e),第二个

30、第二个是是f(e)=f1(e)+b(e)sv1v310,83,35,56,6v2v47,5t8,84,23,0第一个数字是第一个数字是c(e),第二个第二个是是f*最大流最大流11。sv1v310,23,35,36,2v2v47,5t8,44,23,2(s,)（s,+,8）（v3,+,4）（v3,-,2）sv1v310,23,35,36,2v2v47,5t8,44,23,2(s,)（s,8）（v3,+,4）（v3,-,1）（v4,+,4）sv1v310,23,35,36,2v2v47,5t8,44,23,2(s,)（s,8）（v3,+,4）（v3,-,1）（v4,+,4）sv1v310,63,

31、35,36,6v2v47,5t8,84,23,2增流增流(s,)（s,+,4）（v3,-,2）（v2,+,2）sv1v310,63,35,36,6v2v47,5t8,84,23,2增流增流sv1v310,73,35,46,6v2v47,5t8,84,23,1三、最小费用最大流三、最小费用最大流一一批批货货物物要要从从工工厂厂运运至至车车站站，可可以以有有多多条条线线路路进进行行选选择择，在在不不同同的的线线路路上上每每吨吨货货物物的的运运费费不不同同，且且每每条条线线路路的的运运输输能能力力有有限限。怎怎样样运运输输才才能能使费用最少使费用最少?用用结结点点s代代表表工工厂厂，t代代表表车车站

32、站，线线路路为为边边，线线路路的的交交点点为为网网络络的的结结点点，每每条条边边都都有有两两个个权权：容容量量c和和单单位位费费用用a，于于是是构构成成网网络络流流图图N，问问题题变变成求成求N的最小费用流。的最小费用流。一个旅行社接待的一批客人第二天要从甲地一个旅行社接待的一批客人第二天要从甲地飞往乙地，怎样安排才能使旅费最省？飞往乙地，怎样安排才能使旅费最省？这也是一个最小费用流问题，网络的结点是这也是一个最小费用流问题，网络的结点是甲乙两地之间的各个机场，边表示第二天的各个甲乙两地之间的各个机场，边表示第二天的各个航班，其容量是该航班有效座位数，而费用则是航班，其容量是该航班有效座位数，

33、而费用则是该航班的机票费。该航班的机票费。设有一个网络设有一个网络N(V,E)，V=s,a,b,c,t，E中的中的每条边每条边(i,j)对应一个容量对应一个容量cij，输送单位流量所需，输送单位流量所需费用为费用为aij。如有一个运输方案（可行流），流量为。如有一个运输方案（可行流），流量为fij，w是要求从是要求从s到到t的流量。于是最小费流（最小的流量。于是最小费流（最小费用最大流）问题可以描述如下：费用最大流）问题可以描述如下：约束条件约束条件确定最小费最大流的过程实际上是一个多次迭确定最小费最大流的过程实际上是一个多次迭代的过程。基本思想是：从零流为初始可行流开代的过程。基本思想是：从

34、零流为初始可行流开始，在每次迭代过程中对每条边赋予与始，在每次迭代过程中对每条边赋予与c(i,j)（容量（容量）、）、a(i,j)（单位流量运输费用）、（单位流量运输费用）、f(i,j)（现有流的（现有流的流量）有关的权数流量）有关的权数(i,j)，形成一个有向赋权图。，形成一个有向赋权图。再用求最短距离路径的方法确定由发点再用求最短距离路径的方法确定由发点s至收点至收点t的的费用最小的可增流路，沿着该路增加流量，得到费用最小的可增流路，沿着该路增加流量，得到相应的新流。经过多次迭代，直至达到最大流为相应的新流。经过多次迭代，直至达到最大流为止。止。最小费用流算法最小费用流算法把费用看做是该边

35、的长度，则寻找一条从把费用看做是该边的长度，则寻找一条从s到到t的最短的增的最短的增流路，它的费用增长的也就最小。如果最后的流值达到流路，它的费用增长的也就最小。如果最后的流值达到w，这时的费用一般应是最小。，这时的费用一般应是最小。1.初始流分布初始流分布f0使每条边使每条边e都为都为f(e)=0,亦即亦即w0=0.2.在当前可行流分布下修改各边在当前可行流分布下修改各边(i,j)的费用的费用aij*,构造权的方法如下：构造权的方法如下：对任意边（对任意边（i,j），根据现有的流），根据现有的流f，该边上的流，该边上的流量可能增加，也可能减少。因此，每条边赋予向量可能增加，也可能减少。因此，

36、每条边赋予向前费用权前费用权+(i,j)与向后费用权与向后费用权-(i,j）：对于赋权后的有向图，如把权对于赋权后的有向图，如把权(i,j)看作长度，看作长度，即可确定即可确定s到到t的费用最小的非饱和路，等价于从的费用最小的非饱和路，等价于从s到到t的最短路。确定了可增流路后，就可确定该的最短路。确定了可增流路后，就可确定该路的最大可增流量。因此需对每一条边确定一个路的最大可增流量。因此需对每一条边确定一个向前可增流量向前可增流量+(i,j)与向后可增流量与向后可增流量-(i,j)：因此，确定最小费用最大流的具体算法如下：因此，确定最小费用最大流的具体算法如下：(1)从零流开始，令从零流开始，令f0。(2)赋权赋权(3)确定一条从确定一条从s到到t的最短路的最短路P(s,t)(s,i1)，(i1,i2)，(ik,t)若若P(s，t)的长度为的长度为，表明已得到最小费用，表明已得到最小费用最大流，则停止；否则转向最大流，则停止；否则转向(4)。(4)确定沿着该路确定沿着该路P(s，t)的最大可增流量的最大可增流量min(s,i1),(i1,i2),，(ik,t)其中根据边的取向决定取其中根据边的取向决定取或或。(5)生成新的流生成新的流若若f(i,j)已为最小费用最大流，则停止；否则转向已为最小费用最大流，则停止；否则转向(2)。