圖與網(wǎng)絡(luò)模型的基本概念

第十一章圖與網(wǎng)絡(luò)模型§1圖與網(wǎng)絡(luò)的基本概念§2最短路問題§3最小生成樹問題§4最大流問題§5最小費(fèi)用最大流問題1§1圖與網(wǎng)絡(luò)的基本概念圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系。例如：在一個(gè)人群中，對相互認(rèn)識這個(gè)關(guān)系我們可以用圖來表示，圖11-1就是一個(gè)表示這種關(guān)系的圖。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5圖11-12§1圖與網(wǎng)絡(luò)的基本概念

當(dāng)然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的，如對趙等七人的相互認(rèn)識關(guān)系我們也可以用圖11-2來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5圖11-23§1圖與網(wǎng)絡(luò)的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳圖11-3如果我們把上面例子中的“相互認(rèn)識”關(guān)系改為“認(rèn)識”的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧。圖11-3就是一個(gè)反映這七人“認(rèn)識”關(guān)系的圖。相互認(rèn)識用兩條反向的弧表示。4§1圖與網(wǎng)絡(luò)的基本概念無向圖：由點(diǎn)和邊構(gòu)成的圖，記作G=（V，E）。有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D=（V，A）。連通圖：對無向圖G，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則G為連通圖?；芈罚喝袈返牡谝粋€(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則該路為回路。賦權(quán)圖：對一個(gè)無向圖G的每一條邊(vi,vj)，相應(yīng)地有一個(gè)數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。網(wǎng)絡(luò)：

在賦權(quán)的有向圖D中指定一點(diǎn)，稱為發(fā)點(diǎn)，指定另一點(diǎn)稱為收點(diǎn)，其它點(diǎn)稱為中間點(diǎn)，并把D中的每一條弧的賦權(quán)數(shù)稱為弧的容量，D就稱為網(wǎng)絡(luò)。5§2最短路問題最短路問題：對一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)Vs和Vt找到一條從Vs到Vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。一、求解最短路的Dijkstra算法(雙標(biāo)號法）步驟：1.給出點(diǎn)V1以標(biāo)號(0,s)2.找出已標(biāo)號的點(diǎn)的集合I，沒標(biāo)號的點(diǎn)的集合J以及弧的集合3.如果上述弧的集合是空集，則計(jì)算結(jié)束。如果vt已標(biāo)號（lt,kt），則vs到vt的距離為lt，而從vs到vt的最短路徑，則可以從kt反向追蹤到起點(diǎn)vs而得到。如果vt未標(biāo)號，則可以斷言不存在從vs到vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。4.對上述弧的集合中的每一條弧，計(jì)算sij=li+cij。在所有的sij中，找到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號（scd,c）,返回步驟2。6§2最短路問題例1求下圖中v1到v6的最短路解：采用Dijkstra算法，可解得最短路徑為v1v3v4v6各點(diǎn)的標(biāo)號圖如下：v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v47§2最短路問題例2電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。解：這是一個(gè)求無向圖的最短路的問題。可以把無向圖的每一邊（vi,vj）都用方向相反的兩條?。╲i,vj）和（vj,vi）代替，就化為有向圖，即可用Dijkstra算法來求解。也可直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標(biāo)號的點(diǎn)到未標(biāo)號的點(diǎn)的弧的集合改成已標(biāo)號的點(diǎn)到未標(biāo)號的點(diǎn)的邊的集合即可。V1（甲地）15176244431065v2V7（乙地）v3v4v5v68§2最短路問題例2最終解得：最短路徑v1v3v5v6v7，每點(diǎn)的標(biāo)號見下圖（0,s）V1（甲地）1517624431065(13,3)v2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)9§2最短路問題例3設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費(fèi)，但維修費(fèi)用就高了。請?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：設(shè)備每年年初的價(jià)格表設(shè)備維修費(fèi)如下表年份12345年初價(jià)格1111121213使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用568111810§2最短短路問題例3的解：：將問題轉(zhuǎn)化化為最短路路問題，如如下圖：用vi表示“第i年年初購購進(jìn)一臺新新設(shè)備”,?。╲i,vj）表示第i年年初購購進(jìn)的設(shè)備一直使使用到第j年年初。。把所有弧的的權(quán)數(shù)計(jì)算算如下表：：v1v2v3v4v5v612345611622304159216223041317233141723518611§2最短短路問題(繼上頁)把權(quán)數(shù)數(shù)賦到圖中中，再用Dijkstra算算法求最短短路。最終得到下下圖，可知知，v1到v6的距離是53，最短短路徑有兩兩條：v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)12§3最小小生成樹問問題樹是圖論中中的重要概概念，所謂謂樹就是一一個(gè)無圈的的連通圖。。圖11-11中，(a)就是是一個(gè)樹，，而(b)因?yàn)閳D中中有圈所以以就不是樹樹，(c)因?yàn)椴徊贿B通所以以也不是樹樹。圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)13§3最小小生成樹問問題給了一個(gè)無無向圖G=(V,E)，我們們保留G的的所有點(diǎn)，，而刪掉部部分G的邊邊或者說保保留一部分分G的邊，，所獲得的的圖G，稱稱之為G的的生成子圖圖。在圖11-12中，(b)和(c)都是(a)的生生成子圖。。如果圖G的的一個(gè)生成成子圖還是是一個(gè)樹，，則稱這個(gè)個(gè)生成子圖圖為生成樹樹，在圖11-12中，(c)就是(a)的生生成樹。最小生成樹樹問題就是是指在一個(gè)個(gè)賦權(quán)的連連通的無向向圖G中找找出一個(gè)生生成樹，并并使得這個(gè)個(gè)生成樹的的所有邊的的權(quán)數(shù)之和和為最小。。圖11-12(a)(b)(c)14§3最最小小生生成成樹樹問問題題一、、求求解解最最小小生生成成樹樹的的破破圈圈算算法法算法法的的步步驟驟：：1、、在在給給定定的的賦賦權(quán)權(quán)的的連連通通圖圖上上任任找找一一個(gè)個(gè)圈圈。。2、、在在所所找找的的圈圈中中去去掉掉一一個(gè)個(gè)權(quán)權(quán)數(shù)數(shù)最最大大的的邊邊（（如如果果有有兩兩條條或或兩兩條條以以上上的的邊邊都都是是權(quán)權(quán)數(shù)數(shù)最最大大的的邊邊，，則則任任意意去去掉掉其其中中一一條條））。。3、、如如果果所所余余下下的的圖圖已已不不包包含含圈圈，，則則計(jì)計(jì)算算結(jié)結(jié)束束，，所所余余下下的的圖圖即即為為最最小小生生成成樹樹，，否否則則返返回回第第1步步。。15§3最最小小生生成成樹樹問問題題例4用用破破圈圈算算法法求求圖圖（（a））中中的的一一個(gè)個(gè)最最小小生生成成樹樹v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)圖11-1316§3最小小生成樹問問題例5、某大大學(xué)準(zhǔn)備對對其所屬的的7個(gè)學(xué)院院辦公室計(jì)計(jì)算機(jī)聯(lián)網(wǎng)網(wǎng)，這個(gè)網(wǎng)網(wǎng)絡(luò)的可能能聯(lián)通的途途徑如下圖圖，圖中v1,…,v7表示7個(gè)學(xué)學(xué)院辦公室室，請?jiān)O(shè)計(jì)計(jì)一個(gè)網(wǎng)絡(luò)絡(luò)能聯(lián)通7個(gè)學(xué)院辦辦公室，并并使總的線線路長度為為最短。解：此問題題實(shí)際上是是求圖11-14的的最小生成成樹，這在在例4中已已經(jīng)求得，，也即按照照圖11-13的(f)設(shè)計(jì)計(jì)，可使此此網(wǎng)絡(luò)的總總的線路長長度為最短短，為19百米?！肮芾磉\(yùn)籌籌學(xué)軟件””有專門的的子程序可可以解決最最小生成樹樹問題。v1331728541034v7v6v5v4v2v3圖11-1417§4最大大流問題最大流問題題：給一個(gè)個(gè)帶收發(fā)點(diǎn)點(diǎn)的網(wǎng)絡(luò)，，其每條弧弧的賦權(quán)稱稱之為容量量，在不超超過每條弧弧的容量的的前提下，，求出從發(fā)發(fā)點(diǎn)到收點(diǎn)點(diǎn)的最大流流量。一、最大流流的數(shù)學(xué)模模型例6某某石油公司司擁有一個(gè)個(gè)管道網(wǎng)絡(luò)絡(luò)，使用這這個(gè)網(wǎng)絡(luò)可可以把石油油從采地運(yùn)運(yùn)送到一些些銷售點(diǎn)，，這個(gè)網(wǎng)絡(luò)絡(luò)的一部分分如下圖所所示。由于于管道的直直徑的變化化，它的各各段管道（（vi,vj）的流量cij（容量）也也是不一樣樣的。cij的單位為萬萬加侖/小小時(shí)。如果果使用這個(gè)個(gè)網(wǎng)絡(luò)系統(tǒng)統(tǒng)從采地v1向銷地v7運(yùn)送石油，，問每小時(shí)時(shí)能運(yùn)送多多少加侖石石油？v563522241263v1v2v7v4v3v6圖11-2618§4最大大流問題我們可以為為此例題建建立線性規(guī)規(guī)劃數(shù)學(xué)模模型：設(shè)弧(vi,vj)上流量為為fij，網(wǎng)絡(luò)上的的總的流量量為F，則則有：19§4最大大流問題在這個(gè)線性性規(guī)劃模型型中，其約約束條件中中的前6個(gè)個(gè)方程表示示了網(wǎng)絡(luò)中中的流量必必須滿足守守恒條件，，發(fā)點(diǎn)的流流出量必須須等于收點(diǎn)點(diǎn)的總流入入量；其余余的點(diǎn)稱之之為中間點(diǎn)點(diǎn)，它的總總流入量必必須等于總總流出量。。其后面幾幾個(gè)約束條條件表示對對每一條弧弧(vi,vj)的的流流量量fij要滿滿足足流流量量的的可可行行條條件件，，應(yīng)應(yīng)小小于于等等于于弧弧(vi,vj)的的容容量量cij，并并大大于于等等于于零零，，即即0≤fij≤cij。我我們們把把滿滿足足守守恒恒條條件件及及流流量量可可行行條條件件的的一一組組網(wǎng)網(wǎng)絡(luò)絡(luò)流流{fij}稱稱之之為為可可行行流流，，（（即即線線性性規(guī)規(guī)劃劃的的可可行行解解）），，可可行行流流中中一一組組流流量量最最大大（（也也即即發(fā)發(fā)出出點(diǎn)點(diǎn)總總流流出出量量最最大大））的的稱稱之之為為最最大大流流（（即即線線性性規(guī)規(guī)劃劃的的最最優(yōu)優(yōu)解解））。。我們們把把例例6的的數(shù)數(shù)據(jù)據(jù)代代入入以以上上線線性性規(guī)規(guī)劃劃模模型型，，用用““管管理理運(yùn)運(yùn)籌籌學(xué)學(xué)軟軟件件””，，馬馬上上得得到到以以下下的的結(jié)結(jié)果果：：f12=5，，f14=5，，f23=2，，f25=3，，f43=2，，f46=1，，f47=2，，f35=2，，f36=2，，f57=5，，f67=3。。最最優(yōu)優(yōu)值值（（最最大大流流量量））=10。。20§4最最大大流問問題二、最最大流流問題題網(wǎng)絡(luò)絡(luò)圖論論的解解法對對網(wǎng)絡(luò)絡(luò)上弧弧的容容量的的表示示作改改進(jìn)。。為省省去弧弧的方方向，，如下下圖:(a)和(b)、(c)和(d)的意意義相相同。。用以上上方法法對例例6的的圖的的容量量標(biāo)號號作改改進(jìn)，，得下下圖vivjvivjcij0（a））（b））cijcijvivj（cji）（c））vivjcijcji（d））63522241263v1v2v5v7v4v3v60000000000021§4最最大大流問問題求最大大流的的基本本算法法（1））找出出一條條從發(fā)發(fā)點(diǎn)到到收點(diǎn)點(diǎn)的路路，在在這條條路上上的每每一條條弧順順流方方向的的容量量都大大于零零。如如果不不存在在這樣樣的路路，則則已經(jīng)經(jīng)求得得最大大流。。（2））找出出這條條路上上各條條弧的的最小小的順順流的的容量量pf，通過過這條條路增增加網(wǎng)網(wǎng)絡(luò)的的流量量pf。（3））在這這條路路上，，減少少每一一條弧弧的順順流容容量pf，同時(shí)時(shí)增加加這些些弧的的逆流流容量量pf，返回回步驟驟（1）。。用此方方法對對例6求解解：第一次次迭代代：選選擇路路為v1v4v7?；。ǎ╲4,v7）的順順流容容量為為2，，決定了了pf=2，，改進(jìn)進(jìn)的網(wǎng)網(wǎng)絡(luò)流流量圖圖如下下圖：：63522241263v1v2v5v7v4v3v600000000000420222§4最最大大流問問題第二次次迭代代：選選擇路路為v1v2v5v7。?。ǎ╲2,v5）的順順流容容量為為3，決決定了了pf=3，，改進(jìn)進(jìn)的網(wǎng)網(wǎng)絡(luò)流流量圖圖如下下圖：：第三次次迭代代：選選擇路路為v1v4v6v7?；。ǎ╲4,v6）的順順流容容量為為1，決決定了了pf=1，，改進(jìn)進(jìn)的網(wǎng)網(wǎng)絡(luò)流流量圖圖如下下圖：：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v60000004202203333301323第四次次迭代代：選選擇路路為v1v4v3v6v7?；。ǎ╲3,v6）的順順流容容量為2，決決定了了pf=2，，改進(jìn)進(jìn)的網(wǎng)網(wǎng)絡(luò)流流量圖圖如下下圖：：第五次次迭代代：選選擇路路為v1v2v3v5v7。?。ǎ╲2,v3）的順順流容容量為2，決決定了了pf=2，，改進(jìn)進(jìn)的網(wǎng)網(wǎng)絡(luò)流流量圖圖如下下圖：：22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205§4最最大大流問問題24經(jīng)過第第五次次迭代代后在在圖中中已經(jīng)經(jīng)找不不到從從發(fā)點(diǎn)點(diǎn)到收收點(diǎn)的的一條條路，，路上上的每每一條條弧順順流容容量都都大于于零，，運(yùn)算算停止止。得得到最最大流流量為為10。最大流流量圖圖如下下圖：：22v1v2v5v7v4v3v6123522355§4最最大大流問問題“管理理運(yùn)籌籌學(xué)軟軟件””中還還有專專門的的子程程序用用于解解決最最大流流問題題。25§5最最小小費(fèi)用用最大大流問問題最小費(fèi)費(fèi)用最最大流流問題題：給給了一一個(gè)帶帶收發(fā)發(fā)點(diǎn)的的網(wǎng)絡(luò)絡(luò)，對對每一一條弧?。╲i,vj），除除了給給出容容量cij外，還還給出出了這這條弧弧的單單位流流量的的費(fèi)用用bij，要求一個(gè)個(gè)最大大流F，并并使得得總運(yùn)運(yùn)送費(fèi)費(fèi)用最最小。。一、最最小費(fèi)費(fèi)用最最大流流的數(shù)數(shù)學(xué)模模型例7由由于輸輸油管管道的的長短短不一一，所所以在在例6中每每段管管道（（vi,vj）除了有不不同的的流量量限制制cij外，還還有不不同的的單位位流量量的費(fèi)費(fèi)用bij，cij的單位位為萬萬加侖/小時(shí)時(shí)，bij的單位位為百百元/萬加加侖。。如圖圖。從從采地地v1向銷地v7運(yùn)送石油，怎樣運(yùn)送送才能運(yùn)送最最多的石油并并使得總的運(yùn)運(yùn)送費(fèi)用最小??？求出最大大流量和最小費(fèi)用用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)26§5最小費(fèi)費(fèi)用最大流問問題這個(gè)最小費(fèi)用用最大流問題題也是一個(gè)線線性規(guī)劃的問問題。解：我們用線線性規(guī)劃來求求解此題，可可以分兩步走走。第一步，先求求出此網(wǎng)絡(luò)圖圖中的最大流流量F，這已已在例6中建建立了線性規(guī)規(guī)劃的模型，，通過管理運(yùn)運(yùn)籌學(xué)軟件已已經(jīng)獲得結(jié)果果。第二步，在最最大流量F的的所有解中，，找出一個(gè)最最小費(fèi)用的解解，我們來建建立第二步中中的線性規(guī)劃劃模型如下：：仍然設(shè)弧（vi,vj）上的流量為為fij，這時(shí)已知網(wǎng)網(wǎng)絡(luò)中最大流流量為F，只只要在例6的的約束條件上上，再加上總總流量必須等等于F的約束束條件：f12=f14=F,即即得得此此線線性性規(guī)規(guī)劃劃的的約約束束條條件件，，此此線線性性規(guī)規(guī)劃劃的的目目標(biāo)標(biāo)函函數(shù)數(shù)顯顯然然是是求求其其流流量量的的最最小小費(fèi)費(fèi)用用。。由此此得得到到線線性性規(guī)規(guī)劃劃模模型型如如下下：：27§5最最小小費(fèi)用用最大大流問問題28§5最最小小費(fèi)用用最大大流問問題用管理理運(yùn)籌籌學(xué)軟軟件，，可求求得如如下結(jié)結(jié)果：：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。。其最最優(yōu)值值(最最小費(fèi)費(fèi)用)=145。對對照前前面例例6的的結(jié)果果，可可對最最小費(fèi)費(fèi)用最最大流流的概概念有有一個(gè)個(gè)深刻刻的理理解。。如果我我們把把例7的問問題改改為：：每小小時(shí)運(yùn)運(yùn)送6萬加加侖的的石油油從采采地v1到銷地地v7最小費(fèi)費(fèi)用是是多少少？應(yīng)應(yīng)怎樣樣運(yùn)送送？這這就變變成了了一個(gè)個(gè)最小小費(fèi)用用流的的問題題。一一般來來說，，所謂謂最小小費(fèi)用用流的的問題題就是是：在在給定定了收收點(diǎn)和和發(fā)點(diǎn)點(diǎn)并對對每條條弧(vi,vj)賦權(quán)權(quán)以容容量cij及單位位費(fèi)用用bij的網(wǎng)絡(luò)絡(luò)中，，求一一個(gè)給給定值值f的的流量量的最最小費(fèi)費(fèi)用，，這個(gè)個(gè)給定定值f的流流量應(yīng)應(yīng)小于于等于于最大大流量量F，，否則則無解解。求求最小小費(fèi)用用流的的問題題的線線性規(guī)規(guī)劃的的模型型只要要把最最小費(fèi)費(fèi)用最最大流流模型型中的的約束束條件件中的的發(fā)點(diǎn)點(diǎn)流量量F改改為f即可可。在在例6中只只要把把f12+f14=F改改為f12+f14=f=6得得到了了最小小費(fèi)用用流的的線性性規(guī)劃劃的模模型了了。29§5最最小小費(fèi)用用最大大流問問題二、最小費(fèi)費(fèi)用最大流流的網(wǎng)絡(luò)圖圖論解法對網(wǎng)絡(luò)上弧?。╲i,vj）的（cij,bij）的表示作作如下改動(dòng)動(dòng)，用(b)來表示示(a)。。用上述方法法對例7中中的圖形進(jìn)進(jìn)行改進(jìn)，，得圖如下下頁：vivjvivj（cij,bij）（0,-bij）（a）（b）（cij,bij）（cij,bij）vivj（cji,bji）（cij,bij）vivj（cji,bji）（0,-bji)（0,-bji)（c）（d）30§5最小小費(fèi)用最大大流問題求最小費(fèi)用用最大流的的基本算法法在對弧的標(biāo)標(biāo)號作了改改進(jìn)的網(wǎng)絡(luò)絡(luò)圖上求最最小費(fèi)用最最大流的基基本算法與與求最大流的基基本算法完完全一樣，，不同的只只是在步驟驟（1）中中要選擇一一條總的單位費(fèi)用最最小的路，，而不是包包含邊數(shù)最最小的路。。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖11-2831§5最小小費(fèi)用最大大流問題用上述方法法對例7求求解：第一次迭代代：找到最最短路v1v4v6v7。第一次迭迭代后總總流量為為1，總總費(fèi)用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-2932§5最最小費(fèi)用用最大流流問題第二次迭迭代：找找到最短短路v1v4v7。第二次迭迭代后總總流量為為3，總總費(fèi)用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-3033§5最最小費(fèi)用用最大流流問題第三次迭迭代：找找到最短短路v1v4v3v6v7。第三次迭迭代后總總流量為為5，總費(fèi)費(fèi)用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(3,-4)（2,-3）圖11-3134§5最最小費(fèi)用用最大流流問題第四次迭迭代：找找到最短短路v1v4v3v5v7。第四次迭迭代后總總流量為為6，總費(fèi)費(fèi)用72。(6,6)(3,4)(4,7