图与网络西安电子科技大学经济管理学院

运筹学图与网络分析第十章

图与网络

赵玮主要内容：10.1基本概念10.2最短路问题（一）Bellman最优化原理（二）Dijustra算法（双括号法）（三）通信线路布施问题（四）设备更新问题10.3最小生成树（一）基本概念与理论（二）Kruskal算法（加边法、破圈法）（三）丢边法（破圈法）主要内容：10.4最大流问题（一）基本概念（二）双标号算法10.5最小费用最大流（一）基本概念（二）求解算法§10.1基本概念

1图

def1：一个无向图（简称为图）G是一个有序的二元组，记为G=(V,E)。其中V={V1…Vn}称为G的点集合，E=(eij)称为G的边集合，evj为连接VV与Vj的边。

若N和E均为有限集合，则称为G为有限图，否则称无限图。若G中既没有有限回路（圈），也没有两条边连接同一对点，则称G为简单图。如右图之（a），右图之（b）不是简单图。若G为简单图，且G中每个点对之间均有一条边相连，则称G为完全图。如图（a）是简单图，但不是完全图。

图a图bdef2：一个有向图G是一个有序的二元组，记为G=(V,A)，其中V=(V1V2…Vn)称为G的点集合，A={aij}称为G的弧（有向边）集合，aij是以Vi指向Vj的一条弧。

|V|=n表示G中节点个数为n，此节点个数n也称为图G的阶|A|=m表示有向图G中弧的个数为m任一顶点相关联（连接）的边的数目称为该顶点的次数2连通图def3：在有向图G中,一个点和边的交替序列{VieijVj…VkeklVl}称为G中从点Vi到Vl的一条路，记为A，其中Vi为此路A的起点，Vj为路A的终点；若路A的起点与终点重合,则称A为回路；又若G中点Vi与Vj间存在一条路，则称点Vi与Vj是连通的；若G中任何二点都是连通的，则称G为连通图，或图G为连通的。在无向图中有对应的概念。

有向图路回路无向图链圈3子图

def4：设有两个图：G1=(V1,E1)，G2=(V2,E2)若有，则称G1为G2的子图，记作；若有V1=V2而,则称图G1=(V1,E1)是图G2=(V2,E2)的生成子图（支撑子图）。

例：下示图G1是图G的子图，图G2是图G的生成子图。V1V3V2V4V1V2V4V1V3V2V4（a）图G（b）图G1（c）图G24赋权图（（加权图）与与网路def5：设G是一个个图（（或有有向图图），，若对对G的每一一条边边（或或弧））eij都赋予予一实实数ωij，称其为为该边边（弧弧）的的权，，则G连同其其他弧弧上的的权集集合称称为一一个赋赋权图图，记记作G=(V,E,W)或G=(V,A,W)，，此中W={ωij}，ωωij为对应应边（（弧））eij的权。。若G=(V,E,W)（（或(V,A,W)））为赋权权图，，且在在G的V中指定定一个个发点点（常常记为为Vs）和一个个收点点（记记为Vt），其余点点称为为中间间点，，则称称这样样指定定了发发点与与收点点的赋赋权图图G为网络络。§10.2最最短路路问题题def6：设G=（V,A,W）为一个个赋权权有向向图，，Vs为指定定发点点，Vt为指定定收点点，其其余为为中间间点，，P为G中以Vs到Vt的一条条有向向路，，则称称为路P的长度度，若若有则称为为G中从Vs到Vt的最短路，，为为该该最短短路的的长度度（此此中F为G中所有从从Vs到Vt的全体体有向向路的的集合合）。。最短路路问题题在企企业厂厂址上上选择择，厂厂址布布局，设设备更更新，，网络络线路路安装装等工工程设设计与与企业管管理中中有重重要应应用。。（一））Bellman最最优化化原理理1命命题1：若若P是网络络G中从Vs到Vt的一条条最小小路，，Vl是P中除Vs与Vt外的任任何一一个中中间点点，则则沿P从Vs到Vl的一条条路P1亦必是是Vs到Vl的最小小路。。VsV1VlV2VtP2P1证明（（反证证）：：若P1不是从从Vs到Vl的最小小路，，则存存在另另一条条Vs到Vl的路P2使W(P2)<W(P1)，若记路路P中从Vl到Vt的路为为P3。则有W(P2)+W(P3)<W(P1)+W(P3)=W(P)，此说明明G中存在在一条条从Vs沿P2到Vl沿P3再到Vt的更小小的一一条路路，这这与P使G中从Vs到Vt的一条条最小小路矛矛盾。。2算法思思想：：设G中从Vs到Vt的最小小路P：Vs…Vj…Vk…Vt，则由上上述命命题知知：P不仅是是从Vs到Vt的最小小路，，而且且从Vs到P中任意意中间间点的的最短短路也也在P上，为为此可可采用用如下下求解解思路路：⑴为求得得Vs到Vt的最短短路，，可先先求得得Vs到中间间点的的最短短路，，然后后由中中间点点再逐逐步过过渡到到终点点Vt。⑵在计算算过程程中，，需要要把V中“经经判断断为最最短路路P途径之之点i”和“尚尚未判判断是是否为为最短短路P途径之点j”区分开开来，，可设设置集集合I和J,前者归归入I，后者归归入J，并令算算法初初始时时，I中仅包包含Vs，其他点点全在在J中，然然后随随着求求解过过程的的进行，I中的点点逐渐渐增加加（相相应J中的点点逐渐渐减少），，直到到终点点Vt归入I（相应J=φ），，此时迭代结结束。。I称为已已标号号集合合,J称为未未标号号集合合。⑶为为区分分中间间点Vk是否已已归入入I中以及及逆向向求解解最短短路的的方便便，可可在归归入I中的点点Vj上方给给予双双标号号（lj,Vk），此中lj表示从从Vs到Vj最短路路的距距离，，而Vk则为从从Vs到Vj最短路路P中Vj的前前一一途途径径点点。。⑷为在计计算算机机上上实实现现上上述述求求解解思思想想，，还还需需引引入入G中各各点点间间一一步步可可达达距距离离阵阵D=(dij)n××n，此中中|V|=n⑸以下下介介绍绍的的是是适适用用于于弧弧权权为为正正值值的的有有向向网网络络中中求求最最短短有有向向路路的的Dijkstra算法法，，又又称称双双括括号号法法。。事事实实上上该该算算法法亦亦适适用用于于弧弧权权为为负负值值的的有有向向网网络络求求最最短短路路问问题题。。由图图G建立立一一步步可可达达距距离离阵阵D=(dij)n××n给V1(Vs)括号号(l1,Vk)=(0,s)给出出已已标标号号集集合合I和未未标标号号集集合合J的元元素素对于于给给定定的的I和J，，确定定集集合合A={aij|Vi∈I，，Vj∈J}计算算距距离离给Vk括号号(lk,Vh)lk=lh+WhkI=I+{Vk}J=J––{Vk}A=φφ或J＝＝φφ从Vt逆向向搜搜索索双双括括号号，，可可得得最最小小路路P途径径各各点点及及最最小小路路距距离离ENDNY（二二））Dijkstra算法法（（双双括括号号法法））图一一例1（（教教材材208页））求求G的最最短短路路，，图G形如如下下形形。。解：：利利用用上上述述Dijkstra算法法步步骤骤可可得得表表一一所所示示求求解解过过程程，，并并有有最最短短路路P：：V6V4V3V1，最短短距距离离|P|=2+1+5=8。。512图（（一一））表一一（（例例1求求解解过过程程）例2求求如如下下G之最最小小路路V1V4V2V6V8V5V7333V36666117图二二742解表二二表三三（（例例2求求解解过过程程））由表表三三知知V1V8最短短路路P1：V8V6V2V1最短短路路P2：V8V6V5V3V2V1最短短路路长长|P1|=2+7+4=13|P2|=2+3+3+1+4=1344712332（三三））通通信信线线路路布布设设问问题题（（教教材材P209）例3.甲甲、、乙乙两两地地之之间间的的公公路路网网络络如如图图三三，，电电信信公公司司准准备备在在甲甲、、乙乙两两地地沿沿公公路路沿沿线线架架设设一一光光缆缆线线，，问问应应如如何何架架设设此此线线路路方方案案，，以以使使光光缆缆线线路路架架设设总总长长度度最最短短？？图三三解：：本本例例之之一一步步可可达达距距离离阵阵如如G={V,E,W},V={V1V2V3V4V5V6V7}，本例G为无向图图，求解解过程见见表四W=表四（（例3求求解过程程）①由表四可可得最短路P：V7V6V5V3V1最短距离离|P|=10+4+2+6=22②还可得到到自V1（甲）到任任一中间间点之最最短路，，例如V1V4最短路由由表四可可知为P14V4V5V3V1|P14|=1862410（四）设备备更新问问题（教教材P212）例4.某公司设设备管理理部门欲欲制定一一个五年年期某设设备的更更新计划划，要求求给出这这五年中中购置该该设备的的年份及及购置新新设备的的使用年年限。在此五年年中购置置该设备备的年初初价格见见表五，，设备使使用不同同年限的的维护费费见表六六。年份12345年初价格1111121213表五（（单位：：万元））使用年数0～11～22～33～44～5年维护费用5681118表六（（单位位：万元元/年）解：设Vi—i年初购进进一台新新设备aij—i年初购进进之新设设备使用用到第j年初（j-1年末）ωij—i年初购进进之新设设备使用用到第j年初（j-1年末）之总费用用根据表五五与表六六之有关关数据可可计算ωij详可参见表七七；由表表七可得得W阵如表八八；由表表八可得得有向图四四；将表表八可转转换成一一步可达达阵如表表九，求解过程程见表10。表七（（W计算过程程）表八费费用用阵（单单位：万万元）jiωij图四（（设备备更新有有向图））表九九表10设设备备更新求求解过程程min由表10可知最最短费用用流（相相当于最最短路））P：V6V3V1|P|=53万元V4结论：公司五年年期设备备更新方方案有两两个：A与B，总费用均均为53万元。。A方案：第第1年初初购置设设备使用用到第3年初（（第2年年末），，第3年年初再购购置新设设备使用用到第5年末末（第6年初））B方案：第第1年初初购置设设备使用用到第4年初（（第3年年末），，第4年年初再购购置新设设备使用用到第5年末（（第6年年初）§10.3最最小小生成树树最小生成成树在网网络（电电信网、、公路网网等）设设计与企企业管理理中有重重要应用用。（一）基基本概念念与理论论def7：无圈的连连通图（（无向图图）称为为树，常常记为符号号T。如图五的的（a）为树，（（b）有圈，（c）不连通，，故（b）（c）均非树。。V2V1V5V4V6V3V2V1V5V4V6V3V2V1V5V4V6V3（a）（b）（c）图五五def8：若T是图G的一个生生成子图图而且又又是一棵树，则则称树T是图G的一个生生成树（（又称支支撑树）；；又若树树T=(V1,E1)为图G=(V,E,W)的一个生成成树，令令称称为树T的权（或长度度），则则G中具最小小权的生生成树称称为G的最小生生成树，，亦即若若有则有T*为G的最小生生成树，，此中F为G的全体生成树树的集合合。Th1：：设T=(V,E)是|V|≥3的一个个无向图图，则下下列六个个关于树树的定义义是等价价的：⑴T连通且无无圈⑵T的任何两两个顶点点间均必必有一条条且仅有有一条通通路相连⑶T连通且有有n-1条边，此此中n=|V|⑷T有n-1条边且无无圈，此中n=|V|⑸T无圈，但但在T中任两个个不相邻邻的顶点点间添加加一条边，，则可构构成一条条回路⑹T连通，，但去去掉任任一条条边后后就不不连通通，即即树T是连通通且边边数最最小的的图（二））Kruskal算法（（加边边法，，破圈圈法））1.算算法法思想想：①由Th1(4)结论：：若|V|=n，则树T有n-1条边且且无圈②由def8，最小生生成树树T*是具有有最小小权的的生成成树故可E中各边边按权权大小小排列列设为为W1≤W2≤…≤Wm，对应？？边依依次为为a1,a2,…am，然后将将a1,a2,…依次进进入集集合S，直到获获得S的生成成树T为止（（树的的判断断可由由Th1(4)结论）），则则此树树T必为最小小生成成树。。设G=(V,A,W)，|V|=n，|A|=mS—待生成成的集集合i——S中进入入最小小生成成树的的边序序号j——逐个进进入S的G的边序序号ei+1—S中进入入最小小生成成树的的边jWjajakl1W1a1a232W2a2a55…………mWmama76表11对G中各边边按权权大小小顺序序排列列，不不妨设设为W1≤W2≤…≤Wm填写Wj对应的的各边边aj表11S=φ，i=0，，j=1{aj}∪S构成回回路？？|S|=n-1ei+1=ajS={ei+1}∪Si=i+1j=j+1j=j+1T*=S打印T*ENDYYNN图六六例5（（教材材P218）某大学准备备对其所属属的7个个学院办办公室计算算机联网．．这个网络络的可能联联通的途径径如图七所所示，图中中V1，…，V7表示7个学学院办公室室，边eij为可能联网网的途径。。边上所赋赋的权数为为这条路线线的长度（（单位：百百米）。试试设计一局局域网既能能联结七个个学院办公公室，又能能使网络线线路总长度度为最短。。WjajaklT*W1a1a23*W2a2a35*W3a3a27*W4a4a17*W5a5a67*W6a6a37W7a7a56W8a8a57W9a9a43*W10a10a45W11a11a16G={V,E,W},|V|=7,|E|=11W=(ωij)ωij见图解：依据各各边权自小小到大排列列建立表12，求解解过程见表表13，由由表13得得知最小生生成树T*={a1,a2,a3,a4,a5,a9}W(T*)=1+2+3+3+7=19图七表12表13（（例5求求解过程））例6.利利用加边边法求图八八所示的无无向图G之最小生成成树WjajaklT*W1a1a12*W2a2a13*W3a3a45*W4a4a23W5a5a25*W6a6a24W7a7a34W8a8a35解：G={V,E,V}，|V|=5|E|=8表14V1V2V5V3V412234442图八八表15（（例6求解解过程）（三）丢边边法（破圈圈法）1.算法法原理：丢边法与加加边法相反反，加边法法是以不形形成回路为为准则将S=φ逐步加边以以形成树，，而由于按按边权愈小小愈优先加加进去，故故为最小生生成树，而而丢边法则则是S=E以不形成回回路为准则则逐步丢边边以形成树树，由于是是按边权愈愈大愈优先先丢掉，故故同样为最最小生成树树。设G=(V,E,W)，|V|=n，|E|=m，S—待生成的集集合（逐步步丢边）i—S中丢掉边的的序号j—S中保留边的的序号ei+1—S中丢到的边边e1—S中丢到的边边的全体（（集合）fj+1—S中保留的边边D—S中保留边的的集合由于边个数数为m，树含边的个个数为n-1，故丢掉（形成回回路）边的的个数为m-(n-1)=m-n+1，以此为程序出出口，标志志着最小生生成树形成成依次从大到到小按列同同例5表12。G=(V,E,W)，|V|=n，|E|=m，S=E，，i=0，，j=0，，E1=φ,D=φ选S中最大权之之边S中是否有包包含al的一个回路路i=i+1ei=alS=S-{ei}E1=E1∪{ei}T*=S-E1打印T*的边序列j=j+1fj=alD=D∪{fi+1}i≥m-n-1ENDNNYY图九例6.（同同例5）用丢丢边法求解求解过程见表表16，由于于m-n+1=11-(7-1)=5故i=5时程序终止，，由表知T*=S-{e1~e5}={a1,a2,a3,a4,a5,a9}与前加边法求求解相同，详可参参考教材P218的六个图。表16（（例6求解解价格）5=i=m-n+1§10.4最最大大流问题由前知，一个个指定了收点点和发点的赋赋权图G称为网络，在在网络设计中中研究网络的的流量具有现现实意义，如如交通网络的的车流流量，，通信网络中中的话务流量量，金融网络络中的现金流流量，控制网网络中的信息息流量，供电电网络中的电电流流量等。。人们也常常常希望知道在在既定网络中中能允许通过过的最大流量量，以便对该该网络的利用用程序作出评评价，这就是是所谓的网络络最大流问题题。求解方法法有双标号法法，对偶图法法等。1．网络中弧的的容量与流量量def9：对于一个指指定收、发点点的赋权有向向（无向）图图或网络N＝（V，A，C），弧aij∈A的最大允许通通过能力称为为该弧的容量量，记为cij（cij≥0），全体cij构成之集合记记为C；而通过边aij的实际流量成成为流量，记记为fij，故有0≤fij≤cij。显然若fij≥cij则网络N在aij边将发生堵塞塞现象，这是是人们希望能能避免的现象象。（一）基本概概念2．可行流与最最大流def10：设有网络N＝（V，A，C），称f={fij∣aij∈A}为网络N上的流函数，，简称网络流；满足如如下条件的网网络流称为可可行流，其中v（f）为网络N可行流的总流流量（净流入入量）。（1）容量限制条条件：（2）流量守恒条条件：说明：进入节节点vj的流量＝自节节点vj流出的流量；；fij≡0之零流亦满足足上述条件，，故零流以为为可行流。3．顺向弧、逆逆向弧与可增增路def11：设f是网络N的一可行流，，P是N中从vs到vt的一条路，对对于路P途经的各弧，，若弧的方向向与路的方向向相同，则称称该弧为顺向向弧，若弧的的方向与路的的方向相反，，则称该弧为为逆向弧。若若在路P的一切顺向弧弧（vi，vj）上有fij＜cij，在路P的一切逆向弧弧（vj，vi）上有fji＞0，则称路P是一条关于f的可增路。说明：（1）由def11得知：若在路路P中，存在一条条顺向弧（vi，vj）有fij＝cij（此时称弧为为饱和弧），，或者在路P中存在一条逆逆向弧（vj，vi）有fji＝0，则称路P为不可增路；；（2）在图10所示的网络N中有一可行流流f={fij∣aij∈A}，用蓝字标记记，红字标记记各弧的容量量cij。表17给出了四条从从v1到v7的路是否可增增路的判别理理由。（此f满足流量守恒恒条件与容量量限制条件，，如图10表17jv1到v7的路可增路？理由1v1v2v5v7√顺向弧有fij＜cij2v1v2v5v3v6v7√顺向弧fij＜cij逆向弧有f35＞03v1v4v7×顺向弧有f47＝c474v1v2v3v4v7×顺向弧有f23＝c23，f47＝c47（3）可增路的内内涵可通过下下例得知在图10之可行流f中，对于路v1v2v5v3v6v7途经的各弧中中，若f12，f23增加一个单位位流量，f35减少一个单位位流量，利用用流量守恒条条件，可得一一个如图11的新的可行流流，并并有v（）=10＞9=v（f）。图11由上可知在def11中可增路要求求顺向弧fij＜cij之条件，实际际上说明沿该该弧（vi，vj）还可提高流量△△ij＝cij－fij＞0，另一方面，，为提高流量v（f）还要求该路路的逆向弧降降低流量，而而fji＞0正说明了该逆逆向弧可降低低fji个单位。1．算法思想（（见图12）给定N＝{V，A，C}，任取一可行流f＝{fij}，若无可行流，可取零流。l＝1在f中任取一可增路pl利用标号规则与调整规则对沿着路p的各弧作最大可能调整是否对N中所有路均作调整打印经调整后的最大流f*及最大流量v（f*）取N的一条新可增路pll＝l＋1END图12（二）双标号号算法寻找一可增路pl，l＝1vs标号（s，∞），沿pl寻找vs的下一相邻节点vj按标号规则对vj进行双标号（vj，l（vj））

vs＝vt沿pl从收点vt开始反向搜索途经各弧，按调整规则作流量调整抹去pl上各点之双标号，从而由原可行流f调整为新可行流f1，并有v（f）＜v（f1）是否还有新的可增路打印并输出经调整后的最大流f*＝{fij∣aij∈A}，最大流量v（f*）结束l＝l＋1取N的新的可增路plj＝k，i＝j沿pl寻找vj的相邻的一点vk图13NYYN2．调整步骤（（见图13）3．标号与调整整规则（1）标号规则：：1o若（vi，vj）为顺向弧，，且fij<cij，则给vj标号（vi＋，l（vj）），其中l（vj）＝min（l（vi），cij－fij）；2o若（vi，vj）为逆向弧，，且fji>0，则给vj标号（vi－，l（vj）），其中l（vj）＝min（l（vi），fji）；3o若（vi，vj）为顺向弧但但fij＝cij或（vi，vj）为逆向弧但fji＝0，此时沿该弧弧的路线停止止标号。（2）调整规则：：1o若（vi，vj）为顺顺向弧弧，则则对pl路径的的顺向向弧作作调整整，其其调整整量△△ij＝fij＋l（v）；2o若（vi，vj）为逆逆向弧弧，则则对pl途经的的逆向向弧作作调整整，其其调整整量△△ji＝fji－l（v）；3oG中不在在pl路上的的各弧弧不作作调整整。4．例7（教材材P219）某石油油公司司拥有有一管管道网网络，，使用用此管管道网网络可可将石石油从从采地地v1运往销销地v7，由于于各地地的地地质条条件等等不同同，因因而其其管道道直径径有所所不同同，从从而使使各弧弧的容容量cij（单位位：万万加仑仑/小时））不同同，对对于如如图14所示的的管道道网络络N＝（V，A，C），问问每小小时从从v1往v7能运送送多少少加仑仑石油油？图14解1：若设设弧（（vi，vj）上的的流量量为fij，网络络N上总流流量为为F，则可可建立立如下下LP：maxF＝f12＋f14f12＝f23＋f25f14＝f43＋f46＋f47f23＋f43＝f35＋f36s．tf25＋f35＝f57f36＋f46＝f67f47＋f57＋f67＝f12＋f14fij≤ciji＝1～6，j＝1～7fij≥0i＝1～6，j＝1～7v1v2v3v4v5v6v7v1v2v3v4v5v6v70606000002030000002200030032000000500000050000000C阵利用单纯纯形法可可解得最最大流：：f*＝{f12＝5，f14＝5，f23＝2，f25＝3，f43＝2，f46＝1，f47＝2，f35＝2，f36＝2，f57＝5，f67＝3，v（f*）＝10}解2：（采用用双标号号法求最最大流））求解中寻寻找了五五条可增增路，其其标号过过程与增增流过程程见表18，表18中各可增增路及其其流量调调整过程程见图15。求解结果果与解1相同。图15表18（例7求解过程程）l可增路pl第二个标号l（vj）可调整量l（vt）标号图调整图网络流量v（f）1v1v4v7l（v4）＝6，l（v7）＝22（a）（b）22v1v2v3v5v7l（v2）＝6，l（v3）＝2l（v5）＝2，l（v7）＝22（c）（d）43v1v4v6v7l（v4）＝4，l（v6）＝1l（v7）＝21（e）（f）54v1v2v5v7l（v2）＝4，l（v5）＝3l（v7）＝33（g）（h）85v1v4v3v6v7l（v4）＝3，l（v3）＝3l（v6）＝2，l（v7）＝22（i）（j）10已无可增增路END§10.5最小费用用最大流流在很多网网络（电电信网络络、运输输网络、、计算机机网络））的分析析与设计计问题中中，人们们除关心心网络的的系统容容量外还还要考虑虑费用问问题，以以便建立立一个高高效、低低耗的网网络系统统。这就就是最小小费用最最大流问问题的研研究。def12：设网络络N＝｛V,A｝，除对对每一弧弧a∈A规定了其其容量c(a)外，还给给定一个个数b(a)≥0称为弧a的单位流流量费用用，即有有网络N＝｛V,A,c,b｝称其为为带费用用（代价价）的网网络。设设f是N上的一个个可行流流（从vs到vt），称为为可行流流f的费用。。将N上所有流流量等于于v0的可行流流中费用用最小的的可行流流f称为流量量为v0的最小费费用流，，进一步步当v0又是N中最大流流的流量量时，则则称此f为最小费费用最大大流。（一）基基本概念念例8某石油公公司管道道网，由由于输油油管道的的长短不不一，故故对于不不同的地地段（路路径）有有不同的的容量限限制cij之外，还还有不同同的单位位流量费费用bij，该cij的单位为为万加仑仑/小时，bij的单位为为百元/万加仑，，管道网网络如图图16所示，图图中括号号内的数数字表示示（cij，bij）。解1：设fij表示aij上实际流流量，则则由定义义12可建立如如下LPs.tmax总费用b(f)=145此解与例例7的解显然然不同，，它是在在考虑了了费用目目标后的的结果。。（二）求求解算法法算法原理理：最小小费用最最大流之之算法有有多种，，以下介介绍一种种比较易易理解的的算法。。定理3：设f是流量为为v0的最小费费用流，，p是关于f的可增路路中费用用最小的的可增路路。可增增容量为为δ则沿p增容δ后所得到到的可行行流即即为为的的最小小费用流流。若将N中弧aij的单位费费用bij作为该弧弧的弧长长，则上上述定理理中的““可增路路中费用用最小””可理解解为“可可增容的的最短路路”。（（∵此中中最短的的含义即即为路径径各弧的的费用和和最小））利用上述述定理可可得如下下算法步步骤。图172.算法步骤骤表19l关于fl－1的可