運籌學10-圖與網(wǎng)絡優(yōu)化

第十章

圖與網(wǎng)絡優(yōu)化

(GraphTheoryandNetworkAnalysis)圖的基本概念樹及最小支撐樹最短路問題網(wǎng)絡最大流問題最小費用最大流問題中國郵遞員問題圖論的起源和發(fā)展1736年，Euler哥尼斯堡七橋問題(K?nigsbergBridgeProblem)BACDABCD一筆畫問題1847年，kirchhoff，電網(wǎng)絡，“樹”；1852年，《四色猜想》；1964年，華羅庚，《統(tǒng)籌方法平話》。1857年，Cogley，同分異構(gòu)，“樹”；1956年，杜邦公司，CPM，關(guān)鍵路線法；1958年，美國海軍部，PERT，計劃評審技術(shù)；1962年，管梅谷，《中國郵路問題》；第一節(jié)圖的基本概念一、幾個例子例1

是北京、上海等十個城市間的鐵路交通圖。與此類似的還有電話線分布圖、煤氣管道圖、航空路線圖等。北京天津濟南青島武漢南京上海鄭州連云港徐州例2

分別用點v1,v2,v3,v4,v5分別代表甲、乙、丙、丁、戊五支球隊。若有兩支球隊之間比賽過，就在相應的點之間聯(lián)一條線，且這條線不過其他點。如下圖所示：v1v2v3v4v5可知各隊之間的比賽情況如下：甲——乙、丙、丁、戊乙——甲、丙丙——甲、乙、丁丁——甲、丙、戊戊——甲、丁例3“染色問題”儲存8種化學藥品，其中某些藥品不能存放在同一個庫房里。用v1,v2,…,v8分別代表這8種藥品。規(guī)定若兩種藥品不能存放在一起，則其相應的點之間聯(lián)一條線。如下圖所示：v1v2v3v4v5v6v7v8可知需要4個庫房，其中一個答案是：

{v1}{v2,v4,v7}{v3,v5}{v6,v8}還有其他的答案。二、基本概念

有向圖

由點及弧所構(gòu)成的圖，記為D=(V,A)，

V,A分別是D的點集合和弧集合。

無向圖由點及邊所構(gòu)成的圖。記為G=(V,E),V，E分別是G的點集合和邊集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e3e4e5a6e6

邊兩點之間不帶箭頭的聯(lián)線。如e3v1v4a3

弧兩點之間帶箭頭的聯(lián)線。如a3v1v4e3

端點及關(guān)聯(lián)邊若邊e=[u,v]∈E，則稱u,v

為e的端點，也稱u,v是相鄰的，稱e是點u(及點v)的關(guān)聯(lián)邊。如：v1,v4為e3的端點，v1,v4是相鄰的，e3是v1（v4

）的關(guān)聯(lián)邊。

環(huán)若在圖G中，某個邊的兩個端點相同，則稱e是環(huán)。如e7v1v2v3v4e1e2e3e4e5e6e7

多重邊若兩個點之間有多于一條的邊，稱這些邊為多重邊。如e1,e2

簡單圖一個無環(huán)，無多重邊的圖。

多重圖一個無環(huán)、但允許有多重邊的圖。

點v的次以點vi為端點邊的個數(shù)，記為dG(vi)或d(vi)。v1v2v3v4e1e2e3e4e5e6e7如d(v4)=5d(v2)=4v5

懸掛點次為1的點，如v5

懸掛邊懸掛點的關(guān)聯(lián)邊，如e8e8

孤立點次為0的點

偶點次為偶數(shù)的點，如v2

奇點

次為奇數(shù)的點,如v5

鏈中間點初等鏈圈初等圈簡單圈

v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9

在上圖中,(v1,v2,v3,v4,v5,v3,v6,v7)是一條鏈,但不是初等鏈在該鏈中,v2,v3,v4,v5,v3,v6是中間點(v1,v2,v3,v6,v7)是一條初等鏈(v1,v2,v3,v4,v1)是一個初等圈(v4,v1,v2,v3,v5,v7,v6,v3,v4)是一個簡單圈

連通圖圖G中，若任何兩個點之間，至少有一條鏈，稱為連通圖。否則稱為不連通圖。

連通分圖(分圖)若G是不連通圖，則它的每個連通的部分稱為連通分圖。v1v2v3v4e1e2e3e4e5e6v5v6e7如左圖就是個不連通圖，它是由兩個連通分圖構(gòu)成的。

支撐子圖給定一個圖G=(V,E)，如果圖G’=(V’,E’)，使V’=V及E’

E，則稱G’是G的一個支撐子圖。v1v2v3v4(G)v1v2v3v4(G’)

基礎圖給定一個有向圖D=(V,A)，從D中去掉所有弧上的箭頭，所得到的無向圖稱為基礎圖。記之為G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7

路初等路回路v5

簡單有向圖多重有向圖

權(quán)與網(wǎng)絡在實際應用中，給定一個圖G=（V，E）或有向圖D=（V，A），在V中指定兩個點，一個稱為始點（或發(fā)點），記作v1，一個稱為終點（或收點），記作vn

，其余的點稱為中間點。對每一條弧，對應一個數(shù)，稱為弧上的“權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡。對于網(wǎng)絡（賦權(quán)圖）G=（V，E），其中邊有權(quán)，構(gòu)造矩陣，其中：稱矩陣A為網(wǎng)絡G的權(quán)矩陣。設圖G=（V，E）中頂點的個數(shù)為n，構(gòu)造一個矩陣

，其中：稱矩陣A為網(wǎng)絡G的鄰接矩陣。圖的矩陣表示權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437圖的矩陣表示

定理1圖G=(V,E)中，所有點的次之和是邊數(shù)的兩倍，即

定理2任一圖中奇點的個數(shù)為偶數(shù)。三、基本定理第二節(jié)樹一、定義例1在五個城市之間架設電話線，要求任兩個城市之間都可以相互通話（允許通過其他城市），并且電話線的根數(shù)最少。v1v5v2v3v4用v1,v2,v3,v4,v5代表五個城市,如果在某兩個城市之間架設電話線,則在相應的兩點之間聯(lián)一條邊,這樣一個電話線網(wǎng)就可以用一個圖來表示。顯然,這個圖必須是連通的,而且是不含圈的連通圖。如右圖所示。樹的定義：一個無圈的連通圖。例2某工廠的組織機構(gòu)如下圖所示廠長行政辦公室生產(chǎn)辦公室生產(chǎn)計劃科技術(shù)科設計組工藝組供銷科財務科行政科車間鑄造工段鍛壓工段二車間三車間四車間該廠的組織機構(gòu)圖就是一個樹。例3樹圖倒置的樹，根(root)在上，葉(leaf)在下定理1

設圖G=(V,E)是一個樹，p(G)≥2，則G中至少有兩個懸掛點。二、性質(zhì)證明定理2

圖G=(V,E)是一個樹的充分必要條件是G中不含圈，且恰有p-1條邊。證明

定理3

圖G=(V,E)是一個樹的充分必要條件是G是連通圖，并且q(G)=p(G)-1。證明由定理2，必要性顯然。定理4

圖G是樹的充分必要條件是任意兩個頂點之間恰有一條鏈。證明由樹的定義，必要性顯然。因為任兩個頂點間恰有一條鏈，顯然G是連通的。如果G中含有圈的話，則其中至少有兩個頂點間有兩條鏈，這與題設矛盾。充分性得證。推論：

從一個樹中去掉一條邊，則余下的圖是不連通的。

在樹中不相鄰的兩個點間添上一條邊，則恰好得到一個圈。三、圖的支撐樹定義：設圖T=(V,E’)是圖G的支撐子圖，如果圖T=(V,E’)是一個樹，則稱T是G的一個支撐樹。定理：圖G有支撐樹的充分必要條件是圖G是連通的。證明必要性顯然。再證充分性。設圖G是連通圖，若G不含圈，則G本身是一個樹，從而G是它自身的一個支撐樹。

如果G含圈，任取一個圈，從圈中任意地去掉一條邊，得到圖G的一個支撐子圖G1。如果G1不含圈，那么G1是G的一個支撐樹；如果G1仍含圈，那么從G1中任取一個圈，從圈中再任意去掉一條邊，得到圖G的一個支撐子圖G2，如此重復，最終可以得到G的一個支撐子圖Gk,它不含圈，于是Gk是G的一個支撐樹。支撐樹的求解方法

破圈法例用破圈法求解圖的一個支撐樹v1v2v3v4v5e1e2e3e4e5e6e7e8這就得到了該圖的一個支撐樹。

避圈法v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9這就得到了該圖的一個支撐樹。四、最小支撐樹定義1

給圖G=(V,E)，對G中的每一條邊[vi,vj]，相應地有一個數(shù)wij，則稱這樣的圖G為賦權(quán)圖，wij稱為邊[vi,vj]上的權(quán)。1.定義定義2

如果T=(V,E’)是G的一個支撐樹，稱E’中所有邊的權(quán)之和為支撐樹T的權(quán)，記為w(T)，即最小支撐樹如果支撐樹T*的權(quán)w(T*)是G的所有支撐樹的權(quán)中最小者，則稱T*是G的最小支撐樹(簡稱最小樹),即

2.最小支撐樹的求法方法一避圈法

開始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。v1v2v3v4v5v6651572344這就得到了該圖的一個最小支撐樹。方法二破圈法

任取一個圈，從圈中去掉一條權(quán)最大的邊。在余下的圖中，重復這個步驟，一直到一個不含圈的圖為止，這時的圖便是最小樹。v1v2v3v4v5v6651572344這就得到了該圖的一個最小支撐樹。第三節(jié)最短路問題一、最短路問題的提出v1v2v3v4v5v6v7v8v9132216610410423236例左圖為單行線交通網(wǎng)，弧旁數(shù)字表示通過這條單行線所需要的費用。求從v1出發(fā)到v8總費用最小的路線。(1)有很多條路線，與圖論中的路一一對應；(2)一條路線的費用就是相應的路中各條弧的費用之和。如上圖所示的路線為最短路。在圖論中，最短路問題可歸結(jié)為：(1)給定一個賦權(quán)有向圖D＝(V,A)及W(a)=

Wij；(2)給定D中兩個頂點vs、vt，P是D中從vs到vt的一條路；(3)定義路P的權(quán)為P中所有弧的權(quán)之和，W(P)＝

Wij

；(4)求一條權(quán)最小的路P0:W(P0)=minW(P)二、求解方法基本原理：最短路問題的特性最短路線上的任一中間點到終（起）點的路線一定是該中間點到終（起）點的所有路線中最短的路線。若求起點A到任一點G的最短路線，可先求A到G點的相鄰前點的最短距離，在此基礎上求出A到G點的最短距離。這樣，最終求出起點到終點的最短距離。狄克斯屈拉算法

(Dijkstra,1959)。從起點vs出發(fā)，逐步向外探尋最短路。在已知前點的最短距離基礎上，求其后點的最短距離。1.wij0v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,1)第一步：v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)第二步：第三步：v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)第四步：v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)第五步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)第六步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)第七步：(v5,12)(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v3,5)(v1,3)(v1,1)最后，找出v1到v8的最短路為：(v4,11)(v2,6)(v5,10)(v5,9)(v5,12)缺點：不能解決存在負權(quán)圖的最短路問題。計算步驟：

(1)考察從所有標號點(已求出最短距離的點)出發(fā)的弧的終點vj

(已標號的點除外)

，計算起點vs

到vj的距離dsj(標號值＋Wij)；若vj不存在，算法終止，轉(zhuǎn)(3)。

(2)增加新的標號點。比較所有dsj

，最小者對應的點成為新的標號點，即求出了vs

到某個vj的最短距離dsj*，轉(zhuǎn)(1)。

(3)逆著計算過程反推，找出最短路。DP最短路與Dijkstra最短路的比較相同點：

(1)依據(jù)最短路的特性；

(2)隱含比較了vs

到vj

的所有路線。不同點：

(1)Dijkstra更具普遍性，DP是特例；

(2)DP隱含比較vs

到vj

的所有路線是完整的；Dijkstra隱含比較vs

到vj

的所有路線中，只有一部分是完整的，其它的只是vs

到vj

的路線的一段；

(3)每迭代一次，DP可求出起點至某階段末所有點的最短距離，而Dijkstra只能求出起點至一個中間點的最短距離。2.wij不全0

Dijkstra算法失效，即雖然完整的路線比完整中的片斷距離短，但也不能斷定該完整路線一定最短。只能采用最原始的思想，即找出vs

到vj

的所有路線的權(quán)，才能確定vs

到vj

的最短距離。具體算法如下：設有向圖中有n個點，從vi到vj的最短路線不一定從vi直達vj，也可能經(jīng)過一個、兩個或n－2個中間點才能到達vj

。把從vi直達vj，稱為走一步，經(jīng)過一個中間點稱為走二步，則vi到vj的最短路線最多走n－1步。應用條件：圖中不存在負回路。v1v2v3v4v5v6v7v8表格法6-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,

)(v1,

)(v1,

)(v1,

)例:求v1到圖中其他各點的最短路。走1步時v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,

)(v1,

)(v1,

)(v1,

)(v3,-5)(v3,-7)(v3,-1)(v2,5)(v4,11)(v4,5)(v2,1)走2步時v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v1,

)(v1,

)(v3,-5)(v3,-7)(v3,-1)(v2,1)(v6,0)(v4,5)(v4,-5)(v6,6)走3步時(v5,0)(v2,1)(v4,1)(v2,-3)(v6,0)(v7,4)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v6,6)(v1,

)(v3,-5)(v3,-7)(v3,-1)(v2,-3)(v6,0)(v4,-5)走4步時(v5,-4)(v2,1)(v4,1)(v6,0)(v7,-6)(v8,3)(v8,1)wijd(t)(vi

,vj

)

v1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066說明：表中空格處為+

。缺點：不能解決負回路的情況。3.Floyd（佛洛伊德）算法這里介紹得Floyd（1962年）可直接求出網(wǎng)絡中任意兩點間的最短路。令網(wǎng)絡中的權(quán)矩陣為其中當其他算法基本步驟為：⑴輸入權(quán)矩陣例:求圖中任意兩點間的最短路。⑵計算其中例如：

中不帶角標的元素表示從到的距離（直接有邊），帶角標的元素表示借為中間點時的最短路長。

中不帶角標的元素表示從到的距離（直接有邊），帶角標的元素表示借為中間點時的最短路長。在放開的基礎上，再放開注意到：在放開點的基礎上，再放開考察最短路。注意到：說明所有點經(jīng)過并沒有縮短路程。只有一個新增元素表示任意兩點間的最短路長及其路徑。三、應用舉例例設備更新問題。某企業(yè)使用一臺設備，在每年年初都要決定是購置新設備還是繼續(xù)使用舊的。購置新設備要支付一定的購置費，使用舊設備則要支付維修費。制定一個五年內(nèi)的設備更新計劃，使得總支付費用最少。已知該設備在各年年初的價格為：第一年第二年第三年第四年第五年1111121213已知使用不同時間的設備維修費用為：使用年數(shù)0~11~22~33~44~5維修費用5681118

設以vi(i=1,2,3,4,5)表示“第i年初購進一臺新設備”這種狀態(tài)，以v6表示“第5年末”這種狀態(tài)；以弧(vi,

vj)表示“第i年初購置的一臺設備一直使用到第j年初”這一方案，以wij表示這一方案所需購置費和維修費之和。這樣，可建立本例的網(wǎng)絡模型。于是，該問題就可歸結(jié)為從圖中找出一條從v1到v6的最短路問題。從圖中可以得出兩條最短路：

v1—v3—v6;v1—v4—v6v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)(v1,30)v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)(v1,30)(v1,41)v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)(v1,30)(v1,41)(v3,53)(v4,53)第四節(jié)網(wǎng)絡最大流問題

如下是一運輸網(wǎng)絡，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡的最大流量是多少？vsv2v1v3v4vt432115234一、問題的提出二、求解方法（一）概念1.可行流和最大流

容量限制條件：0

fij

cij

平衡條件：

對于網(wǎng)絡D＝(V，A，C)，網(wǎng)絡D上的流

f指定義在弧集合A上的一個函數(shù)f={fij

}，

fij

為弧aij

的流量。滿足下列條件的流f稱為可行流：

v(f)最大的可行流f稱為最大流，記為f*?？捎靡韵翷P模型求解。

對于任何網(wǎng)絡，其可行流f一定存在。如令fij=0，f為可行流，其v(f)=0。零流弧:

fij

=0的弧

若是網(wǎng)絡中連接起點vs和終點vt的一條鏈，定義鏈的方向是從vs到vt，則鏈上的弧被分成兩類：前向?。夯〉姆较蚺c鏈的方向一致,+表示中前向弧的集合后向?。夯〉姆较蚺c鏈的方向相反,‐表示中后向弧的集合3.前向弧和后向弧零流弧和飽和弧

設f是一可行流，是從vs到vt的一條鏈，若滿足下列條件，則稱之為（關(guān)于流f的）一條增廣鏈：在弧(vi,vj)

+上，0fij<cij(非飽和弧)

在弧(vi,vj)

‐上，0<fijcij

(非零流弧)4.增廣鏈vsv2v1v3v4vt10(5)8(3)4(1)5(2)3(2)6(3)3(3)11(6)17(2)5(1)在左圖中,(vs,v1,v2,v3,v4,vt)是一條增廣鏈,因為

+

和‐中的弧滿足增廣鏈的條件。如：5.可擴充量6.調(diào)整后的弧流量v5v1v2v3v4v6(2,2)(8,3)(3,1)(2,2)(4,1)(2,1)(2,2)(5,3)(二)標號法求最大流(FordFulkerson)例：

思路：從一可行流出發(fā)，檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈，則增大流量，使此鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。v5v1v2v3v4v6(2,2)(8,3)(3,1)(2,2)(4,1)(2,1)(2,2)(5,3)(0,+

)(v1,5)(v3,3)(-v4,1)(v2,1)(v5,1)按

=1進行調(diào)整，可得下圖：第一步：尋找增廣鏈，通過給結(jié)點標號實現(xiàn)第二步：調(diào)整可行流(增廣鏈)的流量v5v1v2v3v4v6(2,2)(8,4)(3,0)(2,2)(4,2)(2,2)(2,2)(5,4)(0,+

)(v1,4)(v3,2)按同樣的步驟找可行流。此時,標號過程無法進行下去，算法結(jié)束。三、標號算法的理論依據(jù)定義vsv2v1v3v4vt432115234截集截量

截集的概念將任何復雜的網(wǎng)絡抽象成兩個點之間的流量關(guān)系：

顯然，若把截集去掉，則從vs到vt的路將不存在。截量制約了從vs到vt的流量。最小截集定理可行流f*是最大流的充要條件是不存在關(guān)于f*的增廣鏈。證明：

該定理證明的充分性部分就是標號法的尋找增廣鏈過程；其必要性部分就是調(diào)整可行流的過程。v5v1v2v3v4v6(2,2)(8,4)(3,0)(2,2)(4,2)(2,2)(2,2)(5,4)(0,+

)(v1,4)(v3,2)例：四、最大流最小截集的標號法舉例(0,+)(vs,6)(-v2,6)(v3,1)(v4,1)(0,)(vs,5)(v2,2)(-v5,2)(v4,2)(0,)(vs,3)(-v2,3)最小截集(0,)(vs,5)(v2,2)(-v5,2)(v4,2)第五節(jié)最小費用最大流問題一、問題的提出v1v2vsv3vt(4,10)(1,8)(6,2)(3,10)(2,5)(1,7)(2,4)二、算法的理論基礎(1)若f是流量為v(f)的所有可行流中費用最小者，而

是關(guān)于f

的所有增廣鏈中費用最小的增廣鏈，那么沿

去調(diào)整f，得到的可行流f’

，就是流量為v(f’)的所有可行流中的最小費用流。這樣，當f’

是最大流時,也就得到了我們所要的最小費用最大流。

由于同一流量存在多個可行流f，所以一定存在費用最小的可行流f。設

是關(guān)于可行流f的一條增廣鏈，以

=1調(diào)整f得到新的可行流f’

，b(f’)比b(f)增加的費用為：把調(diào)整后增加的費用稱為這條增廣鏈

的費用。

已知最小費用流f，問題的關(guān)鍵是如何找到關(guān)于f

的最小費用增廣鏈

，從而沿

去調(diào)整f，得到新的最小費用流f’

。

找關(guān)于f

的最小費用增廣鏈

，等價于求從vs到vt的最短路。vsv2vtv1bs1b21b2t已知下圖為關(guān)于f

的最小費用增廣鏈

其最小費用：bs1+b2t－b21-bs1-b21-b2t從vs到vt的路為vs

v1

v2

vt，距離為bs1+b2t－b21

，與最小費用相等。三、求解方法v1v2vsv3vt4163212解：（1）構(gòu)造賦權(quán)有向圖W（f（0））用標號法求最短路(vs,1)(0,0)v1v2vsv3vt4163212(vs,1)(0,0)(v2,3)v1v2vsv3vt4163212(vs,1)(0,0)(v2,3)(v2,4)v1v2vsv3vt4163212(vs,1)(0,0)(v2,3)(v2,4)(v1,4)由此得到vs到vt的最短路：v1v2vsv3vt(4,10)(1,8)(6,2)(3,10)(2,5)(1,7)(2,4)(vs,1)(v2,3)(v1,4)v1v2vsv3vt(0,10)(0,8)(0,2)(0,10)(0,5)(0,7)(0,4)調(diào)整f（0）=0,弧旁數(shù)字為(fij,cij)。調(diào)整最短路對應的增廣鏈，

=5。(5,8)(5,5)(5,7)（2）構(gòu)造賦權(quán)有向圖W（f（1））v1v2vsv3vt416312-1-2-1v1v2vsv3vt416312-1-2-1用標號法求出最短路：v1v2vsv3vt(0,10)(5,8)(0,2)(0,10)(5,5)(5,7)(0,4)調(diào)整最短路對應的增廣鏈，

=2。(2,10)(7,7)（3）構(gòu)造賦權(quán)有向圖W（f（2））v1v2vsv3vt4163-12-1-2-4用標號法求出最短路：v1v2vsv3vt4163-12-1-2-4調(diào)整最短路對應的增廣鏈，

=3。v1v2vsv3vt(0,10)(5,8)(0,2)(0,10)(5,5)(5,