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

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

图与网络

赵玮主要内容：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形如下形黎。解：利百用上述Dijk鸟stra算法步户骤可得小表一所廊示求讽解过程症，并有牌最短路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|=1寺862410（四）设循备更新松问题（限教材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由表1乳0可知骑最短费坛用流（姨相当于搁最短路功）P：择V6V3V1|P|=映53万元V4结论：公司五年膀期设备更器新方案有青两个：A与B，总费用均萍为53万盟元。A方案：龄第1年克初购置刃设备使尺用到第真3年初侨（第2起年末）如，第3愿年初再窑购置新云设备使咐用到第让5年在末（第每6年初驶）B方案：第拴1年初购现置设备使烈用到第4拿年初（第渠3年末）扶，第4年隔初再购置傲新设备使按用到第5离年末（第惨6年初）§10筐.3矛最夏小生成盐树最小生炉成树在鼓网络（臂电信网骑、公路致网等）容设计与驴企业管家理中有存重要应甲用。（一）粱基本概脖念与理偏论def栽7：无圈的好连通图拍（无向尽图）称疑为树，论常记为符满号T。如图五今的（a）为树，（b）有圈，（c）不连通纸，故（b）（c疾）均非树。V2V1V5V4V6V3V2V1V5V4V6V3V2V1V5V4V6V3（a）（b）（c）图旱五def加8错：若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是连通且绸边数最小振的图（二）Krus第kal算法（挖加边法佩，破圈崇法）1.汽算法思柔想：①由Th1(饿4)结论：旦若|V|=n，则树T有n-1条边且无圈②由def港8，最小生成猫树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稍+1腿j劫=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|=1皂1W=(ω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腥+1劲ei=alS=趋S-塑{ei}E1=E1∪{ei}T*=S梨-E1打印T*的边序列j=j缠+1预fj=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．可行秤流与最洲大流def想10：设有网节络N＝（V，A，C），称f={捞fij∣aij∈A}为网络N上的流夏函数，捆简称网络流；满传足如下条秧件的网络帆流称为可脖行流，其中v（f）为网找络N可行流拌的总流蛙量（净晚流入量美）。（1）容量限范制条件：（2）流量守昆恒条件：说明：茫进入节第点vj的流量筑＝自节诉点vj流出的流找量；fij≡0之零流亦蒸满足上述规条件，故菜零流以为秤可行流。3．顺向弧凑、逆向弧传与可增路def1内1：设f是网络N的一可行依流，P是N中从vs到vt的一条路嗽，对于路P途经的各带弧，若弧叼的方向与潜路的方向孝相同，则偏称该弧为劝顺向弧，衣若弧的方师向与路的纲方向相反待，则称该执弧为逆向权弧。若在烘路P的一切领顺向弧待（vi，vj）上有fij＜cij，在路P的一切登逆向弧证（vj，vi）上有fji＞0，则称潜路P是一条关乓于f的可增蒜路。说明：（1）由def鬼11得知：若湿在路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由上可知知在def1木1中可增路翠要求顺向设弧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：max云F＝f12＋f14f12＝f23＋f25f14＝f43＋f46＋f47f23＋f43＝f35＋f36s．t顿f25＋f35＝f57f36＋f46＝f67f47＋f57＋f67＝f12＋f14fij≤ciji＝1～6，j＝1～7fij≥0修i＝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最小费用卸最大流在很多网轧络（电信护网络、运明输网络、按计算机网过络）的分侄析与设计肺问题中，渠人们除关疏心网络的班系统容量膀外还要考拦虑费用问懂题，以便特建立一个域高效、低拨耗的网络参系统。这毯就是最小膏费用最大题流问题的存研究。def1调2：设网络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的可增容最短路pl最短路长︱pl︱可调容量l（vt）系统容量v（f）总费用1v1v4v6v71011102v1v4v71123323v1v4v3v6v71225564v1v4v3v5v71616725v1v2v5v71739123