熊偉編《運籌學(xué)》Ch6網(wǎng)絡(luò)模型

1、2021-10-14 運運 籌籌 學(xué)學(xué) Operations Research Chapter 6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型Network Modeling6.1 最小最小(支撐支撐)樹問題樹問題 Minimal (Spanning)Tree Problem6.2 最短路問題最短路問題 Shortest Path Problem 6.3 最大流問題最大流問題 Maximal Flow Problem6.4 旅行售貨員與中國郵路問題旅行售貨員與中國郵路問題 Traveling Salesman and China Carrier Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Pa

2、ge 2 2021-10-14 哥尼斯堡七橋問題 CDABABCD因為圖因為圖 2 2中的每個點都只與奇數(shù)條線相關(guān)聯(lián)中的每個點都只與奇數(shù)條線相關(guān)聯(lián), ,不不可能將這個圖不重復(fù)地一筆畫成?？赡軐⑦@個圖不重復(fù)地一筆畫成。 Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 3 2021-10-14 點和線畫出各種各樣的示意圖 此圖反映了這七個城市間的鐵路分布情況。這里用點代表城市,用點和點之間的聯(lián)線代表這兩個城市之間的鐵路線。諸如此類的還有 線分布圖,煤氣管道圖,航空線圖等等 北京鄭州 武漢 濟(jì)南 徐州 南京 天津Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 4 20

3、21-10-14例例2,2,有甲有甲, ,乙乙, ,丙丙, ,丁丁, ,戊五個球隊戊五個球隊, ,它們之間比賽的情況它們之間比賽的情況, ,也可以用圖表也可以用圖表示出來示出來。已知甲隊和其它各隊都比賽過一次已知甲隊和其它各隊都比賽過一次, ,乙隊和甲丙隊比賽過乙隊和甲丙隊比賽過, ,丙丙隊和乙隊和乙, ,丁隊比賽過丁隊比賽過, ,丁隊和丙丁隊和丙, ,戊隊比賽過戊隊比賽過, ,戊隊和甲戊隊和甲, ,丁隊比賽過丁隊比賽過。 為了反映這個情況為了反映這個情況, ,可以用點可以用點v v1 1, v, v2 2, v, v3 3, v, v4 4, v, v5 5分別代表這五個隊分別代表這五個隊,

4、 ,某兩個隊之間比賽過某兩個隊之間比賽過, ,就在這兩個隊所相應(yīng)的點之間聯(lián)一條線就在這兩個隊所相應(yīng)的點之間聯(lián)一條線, ,這條線這條線不過其它的點不過其它的點, ,如圖所示如圖所示 v v1 1V V2 2V V3 3V V4 4V V5 5圖4V1V2V5V4V3圖5Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 5 2021-10-145v1v2v3v4v5v6843752618圖圖61運籌學(xué)中研究的圖具有下列特征：運籌學(xué)中研究的圖具有下列特征：（1）用點表示研究對象，用邊（有方向或無方向）表示對）用點表示研究對象，用邊（有方向或無方向）表示對象之間某種關(guān)系。象之間某種關(guān)系。

5、（2）強(qiáng)調(diào)點與點之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與）強(qiáng)調(diào)點與點之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀。形狀。（3）每條邊上都賦有一個權(quán)，其圖稱為賦權(quán)圖。實際中權(quán)）每條邊上都賦有一個權(quán)，其圖稱為賦權(quán)圖。實際中權(quán)可以代表兩點之間的距離、費用、利潤、時間、容量等不同的可以代表兩點之間的距離、費用、利潤、時間、容量等不同的含義。含義。（4）建立一個網(wǎng)絡(luò)模型，求最大值或最小值。）建立一個網(wǎng)絡(luò)模型，求最大值或最小值。Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 6 2021-10-14圖的意義圖的意義 因此因此, ,可以說圖是反映對象之間關(guān)系的一種工可以說圖是反映對象之間關(guān)系的一種工

6、具具, ,在一般情況下在一般情況下, ,圖中點的相對位置如何圖中點的相對位置如何, ,點與點點與點之間聯(lián)線的長短曲直之間聯(lián)線的長短曲直, ,對于反映對象之間的關(guān)系對于反映對象之間的關(guān)系, ,并不是重要的并不是重要的。 如例如例2,2,也可以用如圖也可以用如圖4 4所示的圖去反映五個球隊所示的圖去反映五個球隊的比賽情況的比賽情況, ,這與圖這與圖5 5沒有本質(zhì)的區(qū)別沒有本質(zhì)的區(qū)別, ,所以所以, ,圖論圖論中的圖與幾何圖中的圖與幾何圖, ,工程圖等是不同的工程圖等是不同的. . Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 7 2021-10-14 用用G=G=（V V，E E

7、） 表示表示 其中其中V V表示圖表示圖G G的全部頂點的集合的全部頂點的集合 E E表示圖表示圖G G的全部邊的集合的全部邊的集合 v圖由點和邊組成圖由點和邊組成q 圖的基本概念圖的基本概念例如：例如：V=V=（v v1 1, v, v2 2, v, v3 3，v v4 4, v, v5 5, , v v6 6 ），），E=E=（e e1 1, e, e2 2, e, e3 3, e, e4 4, , e e5 5, e, e6 6, e, e6 6, , ）邊與點間的關(guān)）邊與點間的關(guān)聯(lián)情況如下：聯(lián)情況如下：e e4 4e e2 2v v1 1V V2 2V V3 3V V4 4V V5 5

8、V V6 6e e1 1e e3 3e e5 5e e6 6e e7 7q 無向圖無向圖q 有向圖有向圖Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 8 2021-10-14126,Vv vv邊用邊用vi,vj表示或簡記為表示或簡記為i，j，集合記為，集合記為如圖如圖61所示，點集合記為所示，點集合記為12,13,5 6E，邊上的數(shù)字稱為權(quán)，記為邊上的數(shù)字稱為權(quán)，記為wvi,vj、wi，j或或wij，集合記為，集合記為12131456,Wwwww連通的賦權(quán)圖稱為網(wǎng)絡(luò)圖，記為連通的賦權(quán)圖稱為網(wǎng)絡(luò)圖，記為 GV，E，W5v1v2v3v4v5v6843752618圖圖61Ch6 網(wǎng)

9、絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 9 2021-10-14v 點與邊點與邊 每一條邊和兩個節(jié)點關(guān)聯(lián)，一條邊可以用每一條邊和兩個節(jié)點關(guān)聯(lián)，一條邊可以用兩個節(jié)點的標(biāo)號表示（兩個節(jié)點的標(biāo)號表示（i，j）jiv鏈（鏈（Path） 前后相繼的點邊序列前后相繼的點邊序列 P=(1,2),(2,3),(3,4)4231無向圖中的基本概念4231Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 10 2021-10-14v圈圈(Cycle) 起點和終點重合的鏈稱為起點和終點重合的鏈稱為圈圈 =(1,2),(2,4),(4,3),(3,1) 圈中各條邊方向不一定相同圈中各條邊方

10、向不一定相同4231Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 11 2021-10-14v 點與?。ㄓ邢蜻咟c與?。ㄓ邢蜻? 每一條弧和兩個節(jié)點關(guān)聯(lián)，一條弧可以用每一條弧和兩個節(jié)點關(guān)聯(lián)，一條弧可以用兩個節(jié)點的標(biāo)號表示（兩個節(jié)點的標(biāo)號表示（i，j）jiv路徑（路徑（Path） 前后相繼并且方向相同的弧序列前后相繼并且方向相同的弧序列 P=(1,3),(3,2),(2,4)42314231有向圖中的基本概念Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 12 2021-10-14v 回路（回路（Circuit） 起點和終點重合的路徑稱為起點和終點重合的路徑稱為回

11、路回路 =(1,2),(2,4),(4,1) 回路中各條邊方向相同回路中各條邊方向相同4231v 鏈（鏈（Chain） 前后相繼并且方向不一定相同的邊序前后相繼并且方向不一定相同的邊序列稱為列稱為鏈鏈 C=(1,2),(3,2),(3,4)4231有向圖中的基本概念2021-10-146.1 最小最小(支撐支撐)樹問題樹問題 Minimal (Spanning)Tree ProblemCh6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 14 2021-10-144231v子圖子圖 設(shè)G=(V,E)是一個圖,若VV1,EE,且(V,E)是圖,則稱G=(V,E)是G的一個子圖子圖 v生

12、成子圖生成子圖滿足條件V= V的子圖稱為G的生成生成子圖子圖. . 2314231Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 15 2021-10-14v連通圖連通圖 任意兩個節(jié)點之間至少有一條任意兩個節(jié)點之間至少有一條鏈的圖稱為鏈的圖稱為連通圖連通圖24351v樹樹(Tree) 無圈的連通圖稱為樹無圈的連通圖稱為樹 樹中只與一條邊關(guān)聯(lián)的節(jié)點稱樹中只與一條邊關(guān)聯(lián)的節(jié)點稱為為懸掛節(jié)點懸掛節(jié)點4231Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 16 2021-10-14 樹樹 的的 性性 質(zhì)質(zhì)任何樹至少有一個懸掛節(jié)點任何樹至少有一個懸掛節(jié)點243512435

13、124351v如果樹的節(jié)點個數(shù)為如果樹的節(jié)點個數(shù)為m，則邊的個，則邊的個數(shù)為數(shù)為m-1v樹中任意兩個節(jié)點之間只有唯一樹中任意兩個節(jié)點之間只有唯一的一條鏈的一條鏈v在樹的任意兩個不相鄰的節(jié)點之在樹的任意兩個不相鄰的節(jié)點之間增加一條邊，則形成唯一的圈間增加一條邊，則形成唯一的圈Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 17 2021-10-14樹的概念樹的概念 一個無圈并且連通的無向圖稱為樹圖或簡稱樹一個無圈并且連通的無向圖稱為樹圖或簡稱樹(Tree)。組織機(jī)。組織機(jī)構(gòu)、家譜、學(xué)科分支、因特網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)及高壓線路網(wǎng)絡(luò)等構(gòu)、家譜、學(xué)科分支、因特網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)及高壓線路網(wǎng)絡(luò)等都

14、能表達(dá)成一個樹圖都能表達(dá)成一個樹圖 。 可以證明：可以證明：（1）一棵樹的邊數(shù)等于點數(shù)減）一棵樹的邊數(shù)等于點數(shù)減1；（2）在樹中任意兩個點之間添加一條邊就形成圈；）在樹中任意兩個點之間添加一條邊就形成圈；（3）在樹中去掉任意一條邊圖就變?yōu)椴贿B通。）在樹中去掉任意一條邊圖就變?yōu)椴贿B通。 在一個連通圖在一個連通圖G中，中，取部分邊連接取部分邊連接G的所的所有點組成的樹稱為有點組成的樹稱為G的的部分樹部分樹或或支撐樹支撐樹(Spanning Tree )。圖圖62是圖是圖61的的部分樹。部分樹。 v1v2v3v4v5v64321圖圖6276.1 最小樹問題最小樹問題 Minimal tree pro

15、blemCh6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 18 2021-10-146.1.2 最小部分樹最小部分樹將網(wǎng)絡(luò)圖將網(wǎng)絡(luò)圖G邊上的權(quán)看作兩點間的長度（距離、費用、時間），邊上的權(quán)看作兩點間的長度（距離、費用、時間），定義定義G的部分樹的部分樹T的長度等于的長度等于T中每條邊的長度之和，記為中每條邊的長度之和，記為C(T)。 G的所有部分樹中長度最小的部分樹稱為的所有部分樹中長度最小的部分樹稱為最小部分樹最小部分樹，或簡稱，或簡稱為為最小樹最小樹。 最小部分樹可以直接用作圖的方法求解，常用的有破圈法和最小部分樹可以直接用作圖的方法求解，常用的有破圈法和加邊法。加邊法。破圈

16、法破圈法：任取一圈，去掉圈中最長邊，直到無圈。：任取一圈，去掉圈中最長邊，直到無圈。6.1 最小樹問題最小樹問題 Minimal tree problemCh6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 19 2021-10-145v1v2v3v4v5v6843752618圖圖61【例【例6.1】用破圈法求圖】用破圈法求圖61的最小樹。的最小樹。 圖圖64圖圖64就是圖就是圖61的最小部分樹，最小樹長為的最小部分樹，最小樹長為 C(T)=4+3+5+2+1=15。當(dāng)一個圈中有多個相同的最長邊時，不能同時都去掉，只能去當(dāng)一個圈中有多個相同的最長邊時，不能同時都去掉，只能去掉其中任意

17、一條邊。最小部分樹有可能不唯一，但最小樹的長掉其中任意一條邊。最小部分樹有可能不唯一，但最小樹的長度相同度相同 6.1 最小樹問題最小樹問題 Minimal tree problemCh6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 20 2021-10-14加邊法加邊法：取圖：取圖G的的n個孤立點個孤立點v1，v2， vn作為一個支撐作為一個支撐圖，從最短邊開始往支撐圖中添加，見圈回避，直到連通（有圖，從最短邊開始往支撐圖中添加，見圈回避，直到連通（有n1條邊）條邊） v1v2v3v4v5v643521圖圖65在圖在圖65中，如果添加邊中，如果添加邊v1, v2就形成圈就形成圈v

18、1, v2, v4，這時就，這時就應(yīng)避開添加邊應(yīng)避開添加邊v1, v2，添加下一條最短邊，添加下一條最短邊v3, v6。破圈法和加邊。破圈法和加邊法得到樹的形狀可能不一樣，但最小樹的長度相等法得到樹的形狀可能不一樣，但最小樹的長度相等 5v1v3v515v2v4v684375268Min C(T)=156.1 最小樹問題最小樹問題 Minimal tree problemCh6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 21 2021-10-14最小支撐樹權(quán)值為19例題：5231781454762433265Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 22 2

19、021-10-14最小支撐樹權(quán)值為19例題：5231781454762433265Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 23 2021-10-14下一節(jié)：最短路問題下一節(jié)：最短路問題1.樹、支撐樹、最小支撐樹的概念樹、支撐樹、最小支撐樹的概念2.掌握求最小樹的方法：掌握求最小樹的方法： （1）破圈法）破圈法 （2）加邊法）加邊法作業(yè)：作業(yè)：P149 T 1，4，56.1 最小樹問題最小樹問題 Minimal tree problem2021-10-146.2 最短路問題最短路問題 Shortest Path ProblemCh6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Mo

20、del Page 25 2021-10-14237184562421182151124829 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條路線中的各條路線中, ,哪一條的總長度最短哪一條的總長度最短? ?Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 26 2021-10-14最短路問題在實際中具有廣泛的應(yīng)用，如管道鋪設(shè)、線路選擇最短路問題在實際中具有廣泛的應(yīng)用，如管道鋪設(shè)、線路選擇等問題，還有些如設(shè)備更新、投資等問題也可以歸結(jié)為求最短等問題，還有些如設(shè)備更新、投資等問題也可以歸結(jié)為求最短路問題路問題 求最短路有兩種算法：求最短路有兩種算法： 一是求從某一點至其它各點之

21、間最短離的一是求從某一點至其它各點之間最短離的狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法 另一種是求網(wǎng)絡(luò)圖上任意兩點之間最短路的另一種是求網(wǎng)絡(luò)圖上任意兩點之間最短路的Floyd(弗洛伊德弗洛伊德)矩陣算法。矩陣算法。最短路問題，就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩最短路問題，就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路點之間距離最短的一條路 最短路問題的網(wǎng)絡(luò)模型最短路問題的網(wǎng)絡(luò)模型6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 27 2021-10-146101232146

22、75811165圖圖669【例【例6.3】圖】圖66中的權(quán)中的權(quán)cij表示表示vi到到vj的距離（費用、時間），從的距離（費用、時間），從v1修一條公路或架設(shè)一條高壓線到修一條公路或架設(shè)一條高壓線到v7，如何選擇一條路線使距離，如何選擇一條路線使距離最短，建立該問題的網(wǎng)絡(luò)數(shù)學(xué)模型。最短，建立該問題的網(wǎng)絡(luò)數(shù)學(xué)模型。6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 28 2021-10-14【解】【解】 設(shè)設(shè)xij為選擇弧為選擇弧(i，j)的狀態(tài)變量，選擇弧的狀態(tài)變量，選擇弧(i，j)時時xij1，不，不選擇弧

23、選擇弧(i，j)時時xij0，得到最短路問題的網(wǎng)絡(luò)模型：，得到最短路問題的網(wǎng)絡(luò)模型：( , )12( , )( , )57131467min102,3,610( , )ijiji jEijkii jEk iEijZc xxxxxxixxxi jE或1，6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 29 2021-10-14有向圖的狄克斯屈拉有向圖的狄克斯屈拉(Dijkstra)標(biāo)號算法標(biāo)號算法點標(biāo)號：點標(biāo)號：b(j) 起點起點vs到點到點vj的最短路長；的最短路長；邊標(biāo)號：邊標(biāo)號：k(i，j)=b(i)

24、+cij，步驟：步驟：(1)令起點的標(biāo)號；令起點的標(biāo)號；b(s)0。先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點是先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點是vs ,終點是終點是vt ,以以vi為起為起點點vj為終點的弧記為（為終點的弧記為（i，j）,距離為距離為cij (2)找出所有找出所有vi已標(biāo)號已標(biāo)號vj未標(biāo)號的弧集合未標(biāo)號的弧集合 B=(i，j)，如果這樣，如果這樣的弧不存在或的弧不存在或vt已標(biāo)號則計算結(jié)束；已標(biāo)號則計算結(jié)束；(3)計算集合計算集合B中弧中弧k(i，j)=b(i)+cij的標(biāo)號的標(biāo)號(4)選一個點標(biāo)號選一個點標(biāo)號 返回到第返回到第(2)步。步。)(,),( | ),(min)(lbv

25、Bjijiklblj處標(biāo)號在終點6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 30 2021-10-14610123214675811165圖圖6690610129209186161217162432182929【例【例6.4】用】用Dijkstra算法求圖算法求圖66 所示所示v1到到v7的最短路及最短路長的最短路及最短路長 v1 到到v7的最短路為：的最短路為：p17=v1, v2, v3, v5, v7，最短路長為，最短路長為L17=29 6.2 最短路問題最短路問題 Shortest Path

26、Problem 14Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 31 2021-10-14從上例知，只要某點已標(biāo)號，說明已找到起點從上例知，只要某點已標(biāo)號，說明已找到起點vs到該點的最短路到該點的最短路線及最短距離，因此可以將每個點標(biāo)號，求出線及最短距離，因此可以將每個點標(biāo)號，求出vs到任意點的最短到任意點的最短路線，如果某個點路線，如果某個點vj不能標(biāo)號，說明不能標(biāo)號，說明vs不可達(dá)不可達(dá)vj 。6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 32 2021-10-142371845

27、62421182151124829 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條路線中的各條路線中, ,哪一條的總長度哪一條的總長度? ?最短路問題最短路問題（0 0，1 1） 8211（2 2，1 1） Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 33 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條路線中的各條路線中, ,哪一條的總長度哪一條的總長度? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（6 6，3 3） 最短路問題最短路問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network M

28、odel Page 34 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條路線中的各條路線中, ,哪一條的總長度哪一條的總長度? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 最短路問題最短路問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 35 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條路線中的各條路線中, ,哪一條的總長度最短哪一條的總長度最短? ?（0 0，1 1） 23718456242118215112482

29、98211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 811 （8 8，6 6） 15最短路問題最短路問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 36 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條路線中的各條路線中, ,哪一條的總長度哪一條的總長度? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 811 （8 8，6 6） 1520 （1111，6 6） 最短路問題最短路問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network

30、 Model Page 37 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條路線中的各條路線中, ,哪一條的總長度哪一條的總長度? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 811 （8 8，6 6） 1520 （1111，6 6） 13 （1313，7 7） 從從u u1 1到到u u8 8, ,的最短路為的最短路為13,13,路徑為路徑為1-3-6-7-81-3-6-7-8最短路問題最短路問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 3

31、8 2021-10-14237184562421182151124829 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條路線中的各條路線中, ,哪一條的總長度哪一條的總長度? ?（0 0，1 1） 8211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 15118 （8 8，6 6） 20 （1111，6 6） 13 （1313，7 7） 從從u u1 1到到u u8 8, ,的最短路為的最短路為13,13,路徑為路徑為1-3-6-7-81-3-6-7-8最短路問題最短路問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 39 2021-10-142

32、37184566134105275934682求從求從1到到8的最短路徑的最短路徑 最短路問題練習(xí)最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 40 2021-10-14237184566134105275934682min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, y4=1(1,1)(0,1) 最短路問題練習(xí)最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 41 2021-10-14237184566134105275934682min c12,c16,c42,c47=min 0+2

33、,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, y2=2(0,1)(1,1)(2,1) 最短路問題練習(xí)最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 42 2021-10-14237184566134105275934682min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, y6=3(2,1)(1,1)(0,1)y6=3 最短路問題練習(xí)最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 43 2021-10-142371845661341

34、05275934682min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, y7=3(2,1)(1,1)(0,1)(3,1)y7=3 最短路問題練習(xí)最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 44 2021-10-14237184566134105275934682min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, y5=6(2,1)(1,1)(0,1)(3,1)(3,4)(6,7) 最短路問題練習(xí)

35、最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 45 2021-10-14237184566134105275934682min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, y3=8(2,1)(1,1)(0,1)(3,1)(3,4)(6,7)(8,2) 最短路問題練習(xí)最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 46 2021-10-14237184566134105275934682min c38,c58,c78=min 8+6,6+4,

36、3+8=min 14,10,11=10X=1,2,3,4,5,6,7,8, y8=10(2,1)(1,1)(0,1)(3,1)(3,4)(6,7)(8,2)(10,5) 最短路問題練習(xí)最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 47 2021-10-142371845661341052759346821到10的最短路徑為1，4，7，5，8，長度為10。(2,1)(1,1)(0,1)(3,1)(3,4)(6,7)(8,2)(10,5) 最短路問題練習(xí)最短路問題練習(xí)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 48 2021-10-146.2.3

37、 無向圖最短路的求法無向圖最短路的求法無向圖最短路的求法只將上述步驟（無向圖最短路的求法只將上述步驟（2）改動一下即可。）改動一下即可。點標(biāo)號：點標(biāo)號：b(i) 起點起點vs到點到點vj的最短路長；的最短路長；邊標(biāo)號：邊標(biāo)號：k(i，j)=b(i)+cij，步驟：步驟：(1)令起點的標(biāo)號；令起點的標(biāo)號；b(s)0。(3)計算集合計算集合B中邊標(biāo)號：中邊標(biāo)號：ki，j=b(i)+cij)(, | ,min)(lbvBjijiklblj處標(biāo)號在端點(4)選一個點標(biāo)號選一個點標(biāo)號: 返回到第返回到第(2)步。步。 (2)找出所有一端找出所有一端vi已標(biāo)號另一端已標(biāo)號另一端vj未標(biāo)號的邊集合未標(biāo)號的邊

38、集合 B=i，j如如果這樣的邊不存在或果這樣的邊不存在或vt已標(biāo)號則計算結(jié)束；已標(biāo)號則計算結(jié)束；6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 49 2021-10-14【例【例6.5】求圖】求圖6-10所示所示v1到各點的最短路及最短距離到各點的最短路及最短距離4526178393261216180452231039612641166188122482418所有點都已標(biāo)號，點上的標(biāo)號就是所有點都已標(biāo)號，點上的標(biāo)號就是v1到該點的最短距離，最短路到該點的最短距離，最短路線就是紅色的鏈。線就是紅色的鏈。圖圖

39、6-106.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 50 2021-10-14237184562421182151124829 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條鏈中的各條鏈中, ,哪一條的總長度最短哪一條的總長度最短? ?（0 0，1 1） 8211（2 2，1 1） Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 51 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條鏈中的各條鏈中, ,哪一條的總長度最短哪一條的總長度最短? ?（0，1）

40、2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4最短鏈問題最短鏈問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 52 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條鏈中的各條鏈中, ,哪一條的總長度最短哪一條的總長度最短? ?（0，1）2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4516（5 5，4 4） 最短鏈問題最短鏈問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 53 2021-10-14 現(xiàn)問從現(xiàn)問從u u1

41、1到到u u8 8, ,的各條鏈中的各條鏈中, ,哪一條的總長度最短哪一條的總長度最短? ?（0，1）2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4516（5 5，4 4） 7139（6 6，3 3） 最短鏈問題最短鏈問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 54 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條鏈中的各條鏈中, ,哪一條的總長度最短哪一條的總長度最短? ?（0，1）2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 451

42、6（5 5，4 4） 7139（6 6，3 3） 15（7 7，6 6） 最短鏈問題最短鏈問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 55 2021-10-14 現(xiàn)問從現(xiàn)問從u u1 1到到u u8 8, ,的各條鏈中的各條鏈中, ,哪一條的總長度最短哪一條的總長度最短? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4516（5 5，4 4） 7139（6 6，3 3） 15（7 7，6 6） 8（8 8，5 5） 最短鏈問題最短鏈問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Pa

43、ge 56 2021-10-14從從u u1 1到到u u8 8, ,的各條鏈中的各條鏈中, , 最短鏈為最短鏈為1-3-4-6-581-3-4-6-58（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4516（5 5，4 4） 7139（6 6，3 3） 15（7 7，6 6） 8（8 8，5 5） 最短鏈問題最短鏈問題Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 57 2021-10-14對于對于wij0時可用時可用D氏算法，當(dāng)氏算法，當(dāng)wij0時，則可能失效。時，則可能失效。 231-424231-

44、424（0，0）42（2，1）最短路徑為最短路徑為1-2-3 ，最短距離為，最短距離為0因此當(dāng)負(fù)權(quán)時因此當(dāng)負(fù)權(quán)時, 需要用求負(fù)權(quán)最短路問題的需要用求負(fù)權(quán)最短路問題的Filoyd算法算法. 6.2.4 最短路的最短路的Floyd算法算法 Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 58 2021-10-14 Floyd 算法算法回路(u2, u3, u4, u2,)的長是-2,故從u1到u5的最短路的長度無下界,因此在研究最短路問題時,常設(shè)圖中不存在負(fù)回路,在此假設(shè)下,從一點到另一點的最短路總可以取成初等路. 如果一個有向圖如果一個有向圖D中存在權(quán)為負(fù)數(shù)的回路中存在權(quán)為負(fù)數(shù)的

45、回路(稱為負(fù)回路稱為負(fù)回路) ，這樣兩點間最短路的長度就沒有下界。這樣兩點間最短路的長度就沒有下界。 421352132-51Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 59 2021-10-14Floyd算法基本步驟算法基本步驟 :(1)寫出寫出vi一步到達(dá)一步到達(dá)vj 的距離矩陣的距離矩陣 ，L1也是一步到達(dá)的也是一步到達(dá)的最短距離矩陣。如果最短距離矩陣。如果vi 與與vj 之間沒有邊關(guān)聯(lián)，則令之間沒有邊關(guān)聯(lián)，則令cij=+ (1)1()ijLL(2)計算二步最短距離矩陣。設(shè)計算二步最短距離矩陣。設(shè)vi 到到vj 經(jīng)過一個中間點經(jīng)過一個中間點vr 兩步到達(dá)兩步到達(dá)vj，

46、則，則vi到到vj的最短距離為的最短距離為(2)minijirrjrLcc最短距離矩陣記為最短距離矩陣記為 (2)2()ijLL(3)計算計算k步最短距離矩陣。設(shè)步最短距離矩陣。設(shè) vi經(jīng)過中間點經(jīng)過中間點vr 到達(dá)到達(dá)vj，vi 經(jīng)過經(jīng)過k1步到達(dá)點步到達(dá)點vr 的最短距離為的最短距離為 ，vr 經(jīng)過經(jīng)過k1步到達(dá)點步到達(dá)點vj 的最短的最短距離為距離為 ，則，則 vi 經(jīng)經(jīng)k步步 到達(dá)到達(dá)vj 的最短距離為的最短距離為(1)krjL(1)krjL(6.1)6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page

47、 60 2021-10-14( )(1)(1)minkkkijirrjrLLL最短距離矩陣記為最短距離矩陣記為 ( )()kkijLL(4)比較矩陣比較矩陣Lk與與Lk1，當(dāng)，當(dāng)LkLk1時得到任意兩點間的最短距時得到任意兩點間的最短距離矩陣離矩陣Lk。設(shè)圖的點數(shù)為設(shè)圖的點數(shù)為n并且并且cij0，迭代次數(shù)，迭代次數(shù)k由式由式(6.3) 估計得到。估計得到。 (6.2)121221kknlg(1)1lg 2nkk(6.3)6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 61 2021-10-14634521

48、2789326121610【例【例6.6】圖】圖6-14是一張是一張8個城市的鐵路交通圖，鐵路部門要制作個城市的鐵路交通圖，鐵路部門要制作一張兩兩城市間的距離表。這個問題實際就是求任意兩點間的最一張兩兩城市間的距離表。這個問題實際就是求任意兩點間的最短路問題。短路問題?！窘狻俊窘狻?(1)依據(jù)圖依據(jù)圖6-14,寫出寫出任意兩點間一步到達(dá)距離任意兩點間一步到達(dá)距離表表L1。見表所示。本例。見表所示。本例n=8， ，因此計，因此計算到算到L3 圖圖6-14lg72.807lg26.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Mod

49、el Page 62 2021-10-14v1v2v3v4v5v6v7v8v10 06 65 54 4v26 60 03 32 28 8v33 30 07 71616v45 52 20 09 912123 3v58 87 79 90 010106 6v64 412120 02 2v73 310102 20 01212v816166 612120 0表表6-1 最短距離表最短距離表 L16.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 63 2021-10-14表表6-2 最短距離表最短距離表L2v1v2v3

50、v4v5v6v7v8v106951446v26032810514v3930571713v4525095315v514879012106v64105120214v765173102012v8141315614120計算說明：計算說明：L(2)ij等于表等于表6-1中第中第i行與第行與第j列對應(yīng)元素相加取最小值。如列對應(yīng)元素相加取最小值。如 4341134223433344434553466347734883min,min 5,23,0,0,97,0,10,6165Lcccccccccccccccc (2)6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)

51、絡(luò)模型 Network Model Page 64 2021-10-14表表6-3計算示例計算示例: 等于表等于表6-2中第中第i行與第行與第j列對應(yīng)元素相加取最小值。例如，列對應(yīng)元素相加取最小值。例如，v3經(jīng)過三步（最多三個中間點經(jīng)過三步（最多三個中間點4條邊）到達(dá)條邊）到達(dá)v6的最短距離是的最短距離是表表6-3 最短距離表最短距離表L3v1v2v3v4v5v6v7v8v10695144618v2603287514v39305710813v4525095315v514879012106v647105120214v76583102012v818141315614120(3)ijL2222363

52、116322633363886min,min 94,310,0,55,712,0,172,131410LLLLLLLLL (3)(2)(2)(2)(2)6.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 65 2021-10-14【例【例6.7】求圖】求圖615中任意兩點間的最短距離。中任意兩點間的最短距離?！窘狻繄D【解】圖615是一個混合圖，有是一個混合圖，有3條邊的權(quán)是負(fù)數(shù)條邊的權(quán)是負(fù)數(shù),有兩條邊有兩條邊無方向。依據(jù)圖無方向。依據(jù)圖615,寫出任意兩點間一步到達(dá)距離表寫出任意兩點間一步到達(dá)距離表L1。表。

53、表中第一列的點表示弧的起點，第一行的點表示弧的終點，無方中第一列的點表示弧的起點，第一行的點表示弧的終點，無方向的邊表明可以互達(dá)，見表向的邊表明可以互達(dá)，見表6-4所示。計算過程見表所示。計算過程見表6-56-7。445743271028圖圖615156.2 最短路問題最短路問題 Shortest Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 66 2021-10-14表表6-4一步到達(dá)距離表一步到達(dá)距離表L1v1v2v3v4v5v6v7v105 4v2042v34072v440107v5103v6508v7206.2 最短路問題最短路問題 Shor

54、test Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 67 2021-10-14表表6-7 最短距離表最短距離表L4v1v2v3v4v5v6v7v10593419v2204-2635v364021072v44990857v5-14720-35v69141051308v786241290經(jīng)計算經(jīng)計算L4L5，L4是最優(yōu)表。表是最優(yōu)表。表6-7不是對稱表，不是對稱表，vi到到vj與與vj到到vi的的最短距離不一定相等。對于有負(fù)權(quán)圖情形，公式最短距離不一定相等。對于有負(fù)權(quán)圖情形，公式(6.3)失效。失效。 6.2 最短路問題最短路問題 Shortest

55、Path Problem Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 68 2021-10-14 Floyd 算法的內(nèi)容算法的內(nèi)容設(shè)給定有向圖D=(V,E)及E上的權(quán)函數(shù)w(e)以wj表示從vi到vj的最短路的權(quán), w=(vi,vj)仍簡記為wij.又設(shè)V的點數(shù)為n,易知w1, w2, wn,必須滿足如下方程: wj =min wi+wij, (vjV j=1,2,n)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 69 2021-10-14 Floyd 算法的內(nèi)容算法的內(nèi)容 對一切i規(guī)定wii=0, 若V中的兩點vi和vj之間無弧相連,則令w=(vi,vj

56、)=+,這樣便可認(rèn)為,任何兩點之間都有弧相連了. 開始令wj(0)= w1j(j=1,2,n),一般地,設(shè)已有各個wj(k-1),則: wj(k)= min wi(k-1)+ wij (j=1,2,n) 當(dāng)過程進(jìn)行到某一步,發(fā)現(xiàn)每個j都有wj(k)= wj(k-1)時,則計算停止,此時wj(k)就是從vi到vj的最短路的權(quán). 上述算法最多經(jīng)過n-1次迭代必定收斂。若在已算出的wj(n-1)中至少有某個j,使得wj(n-1)wj(n-2), 說明圖中有負(fù)回路，無最短路. 方程方程 wj =min wi+wij 的解可以用迭代法求得的解可以用迭代法求得,步驟如下步驟如下:Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型

57、Network Model Page 70 2021-10-14求求v v1 1到各點的最短路？到各點的最短路？ Floyd 算法示例算法示例433-4-27-132315-22254Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 71 2021-10-14 Floyd 算法示例算法示例 求解過程可在表上進(jìn)行。表的左邊是初始數(shù)據(jù)，右邊是各次迭代的計算結(jié)果，最右邊的一列數(shù)字就是從V1到各個VJ的最短路的權(quán)。Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 72 2021-10-14Floyd 算法示例算法示例wijv1v2v3v4v5v1 023v220-2v3-2

58、-40v4530-1v53740Wj(0) 0 2(1,2) 3(1,3) Wj(1) 0 -1(3,2) 3(1,3) 0(2,5)Wj(2) 0 -1(3,2) 3(1,3) 3(1,3) 3(1,3) 0 0 -1(3,2) -1(3,2) 4(5,4) 1(5,4) 1(5,4) -3(2,5) -3(2,5) -3(2,5)Wj(3)Wj(4)Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 73 2021-10-14 Floyd 算法示例算法示例 求求Wj(0) Wj(0) = W1j W11 = 0 W12 = 2 (1,2) W13 = 3 (1,3) W14 =

59、 W15 = Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 74 2021-10-14 Floyd 算法示例算法示例 求求Wj(1) Wj(1) = min Wi(0) + Wij W1(1) = min W1(0) + W11、 W2(0) + W21 W5(0) + W51 = min0+0、2+2、3-2=0 W2(1) = min W1(0) + W12、 W2(0) + W22 W5(0) + W52 = min0+2、2+0、3-4=-1（3，2） W3(1) = min W1(0) + W13、 W2(0) + W23 W5(0) + W53 = min0+3、

60、3+0=3（1，3） W4(1) = min W1(0) + W14、 W2(0) + W24 W5(0) + W53 = W5(1) = min W1(0) + W15、 W2(0) + W25 W5(0) + W55 = min2-2=0（2，5）Ch6 網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Model Page 75 2021-10-14 Floyd 算法示例算法示例 求求Wj(2) Wj(2) = min Wi(1) + Wij W1(2) = min W1(1) + W11、 W2(1) + W21 W5(1) + W51 = min0+0、-1+2、3-2=0 W2(2) = min