第6章最短路問(wèn)題

1、運(yùn)運(yùn) 籌籌 學(xué)學(xué) ( Operations Research ) 運(yùn)運(yùn) 籌 籌 帷 帷 幄 幄 之 之 中 中 決決 勝 勝 千 千 里 里 之 之 外 外 圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析 Graph Theory and Network Analysis Graph Theory and Network Analysis 第六章第六章 如何用最短的線(xiàn)路將三部電話(huà)連起來(lái)？如何用最短的線(xiàn)路將三部電話(huà)連起來(lái)？ 此問(wèn)題可抽象為設(shè)此問(wèn)題可抽象為設(shè)ABC為等邊三角形，連接三頂點(diǎn)的路為等邊三角形，連接三頂點(diǎn)的路 線(xiàn)（稱(chēng)為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線(xiàn)者顯然線(xiàn)（稱(chēng)為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線(xiàn)者

2、顯然 是二邊之和（如是二邊之和（如ABAC）。）。 A BC A B C P 但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)P），連接），連接4點(diǎn)的新網(wǎng)絡(luò)的最短路點(diǎn)的新網(wǎng)絡(luò)的最短路 線(xiàn)為線(xiàn)為PAPBPC。最短新路徑之長(zhǎng)。最短新路徑之長(zhǎng)N比原來(lái)只連三點(diǎn)的最比原來(lái)只連三點(diǎn)的最 短路徑短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且 穩(wěn)定性也更好。穩(wěn)定性也更好。 問(wèn)題描述：?jiǎn)栴}描述： 就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間 距離最短的一條路距離最短的一條路 . 有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選

3、線(xiàn)、設(shè)備更新、投有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線(xiàn)、設(shè)備更新、投 資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短 路的問(wèn)題。因此這類(lèi)問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。路的問(wèn)題。因此這類(lèi)問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。 一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過(guò)河一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過(guò)河 到北岸，河上只有一條獨(dú)木舟，每次除了人以外，只能帶一到北岸，河上只有一條獨(dú)木舟，每次除了人以外，只能帶一 樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜， 問(wèn)應(yīng)該怎樣安排渡河，

4、才能做到既把所有東西都運(yùn)過(guò)河去，問(wèn)應(yīng)該怎樣安排渡河，才能做到既把所有東西都運(yùn)過(guò)河去， 并且在河上來(lái)回次數(shù)最少？這個(gè)問(wèn)題就可以用求最短路方法并且在河上來(lái)回次數(shù)最少？這個(gè)問(wèn)題就可以用求最短路方法 解決。解決。 定義：定義： 1）人）人M（Man），狼），狼W（Wolf），）， 羊羊G（Goat），）， 草草H（Hay） 2） 點(diǎn)點(diǎn) vi 表示河岸的狀態(tài)表示河岸的狀態(tài) 3） 邊邊 ek 表示由狀態(tài)表示由狀態(tài) vi 經(jīng)一次渡河到狀態(tài)經(jīng)一次渡河到狀態(tài) vj 4） 權(quán)權(quán)邊邊 ek 上的權(quán)定為上的權(quán)定為 1 我們可以得到下面的加權(quán)有向圖我們可以得到下面的加權(quán)有向圖 狀態(tài)說(shuō)明：狀態(tài)說(shuō)明： v1,u1 =( M

5、,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G) 此游戲轉(zhuǎn)化為在下面的二部圖中求從此游戲轉(zhuǎn)化為在下面的二部圖中求從 v1 到到 u1 的最短路問(wèn)題。的最短路問(wèn)題。 v1v2v3v4v5 u5u4u3u2u1 求最短路有兩種算法求最短路有兩種算法: 狄克斯屈拉狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法標(biāo)號(hào)算法 逐次逼近算法逐次逼近算法 若序列若序列 vs,v1.vn-1,vn 是從是從vs到到vn間間的最短路，則序列的最短路，則序列 vs,v1.vn-1 必為從必為從vs 到到vn-1的最短路。的最短路。 假定

6、假定v1v2 v3 v4是是v1 v4的最短路，則的最短路，則v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4 的最短路。的最短路。 v1 v2 v3 v4 v5 求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點(diǎn)是求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點(diǎn)是vs,終點(diǎn)是終點(diǎn)是vt ,以以vi為起點(diǎn)為起點(diǎn)vj 為終點(diǎn)的弧記為為終點(diǎn)的弧記為 (i, j) 距離為距離為dij ：b(j) 起點(diǎn)起點(diǎn)vs到點(diǎn)到點(diǎn)vj的最短路長(zhǎng)；的最短路長(zhǎng)； ： k(i,j)=b(i)+dij， 步驟：步驟： 1. 令起點(diǎn)的標(biāo)號(hào)；令起點(diǎn)的標(biāo)號(hào)；b(s)0。 2. 找出所有找出所有vi已標(biāo)號(hào)已標(biāo)號(hào)vj未標(biāo)

7、號(hào)的弧集合未標(biāo)號(hào)的弧集合 B=(i, j) 如果這樣的如果這樣的 弧不存在或弧不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束；已標(biāo)號(hào)則計(jì)算結(jié)束； 3. 計(jì)算集合計(jì)算集合B中弧中弧k(i，j)=b(i)+dij的標(biāo)號(hào)的標(biāo)號(hào) 4. 選一個(gè)點(diǎn)標(biāo)號(hào)選一個(gè)點(diǎn)標(biāo)號(hào) 在終點(diǎn)在終點(diǎn)vl處標(biāo)處標(biāo) 號(hào)號(hào)b(l), 返回到第返回到第2步。步。 ,),( | ),(min)(Bjijiklb j 例例6.5 求下圖求下圖v1到到v7的最短路長(zhǎng)及最短路線(xiàn)的最短路長(zhǎng)及最短路線(xiàn) 8 6 2 5 23 5 3 4 2 10 5 7 0 8 6 2 2 5 4 4 11 14 7 5 10 7 11 P標(biāo)號(hào)標(biāo)號(hào) T標(biāo)號(hào)標(biāo)號(hào) 9 v1到到v7的最

8、短路長(zhǎng)及最短路線(xiàn)如圖所示：的最短路長(zhǎng)及最短路線(xiàn)如圖所示： 8 6 2 5 23 5 3 4 2 10 5 7 v7已標(biāo)號(hào)，計(jì)算結(jié)束。從已標(biāo)號(hào)，計(jì)算結(jié)束。從v1到到v7的最短路長(zhǎng)是的最短路長(zhǎng)是 11, 最短路線(xiàn)：最短路線(xiàn)： v1 v4 v6 v7 0 2 4 11 從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)vs到到 該點(diǎn)的最短路線(xiàn)及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)該點(diǎn)的最短路線(xiàn)及最短距離，因此可以將每個(gè)點(diǎn)標(biāo) 號(hào)，求出號(hào)，求出vs到任意點(diǎn)的最短路線(xiàn)，如果某個(gè)點(diǎn)到任意點(diǎn)的最短路線(xiàn)，如果某個(gè)點(diǎn)vj不能不能 標(biāo)號(hào)，說(shuō)明標(biāo)號(hào)，說(shuō)明vs不可達(dá)不可達(dá)vj 。 注：無(wú)向圖最短路

9、的求法只將上述步驟注：無(wú)向圖最短路的求法只將上述步驟2將弧改成邊即可。將弧改成邊即可。 例例6.6 求下圖求下圖v1到各點(diǎn)的最短距離及最短路線(xiàn)。到各點(diǎn)的最短距離及最短路線(xiàn)。 4 5 2 6 1 7 8 3 9 3 2 6 12 16 18 0 4 5 2 2 3 10 3 96 12 6 4 11 6 6 18 8 12 24 8 24 18 v1到各點(diǎn)的最短距離及最短路線(xiàn)如圖所示：到各點(diǎn)的最短距離及最短路線(xiàn)如圖所示： 4 5 2 6 1 7 8 3 9 3 2 6 12 16 18 0 2 6 18 所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是v1到該點(diǎn)的最短距離，最短到該點(diǎn)

10、的最短距離，最短 路線(xiàn)就是紅色的鏈。路線(xiàn)就是紅色的鏈。 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 例例6.7 求從求從1 1到到8 8的最短路徑的最短路徑 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 X=1, w1=0 min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, p4=1 p4=1 p1=0 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 X=1,4 min c12,c16,c42,c47=min 0+2,0+3,1+1

11、0,1+2=min 2,3,11,3=2 X=1,2,4, p2=2 p1=0 p4=1 p2=2 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 X=1,2,4 min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, p6=3 p2=2 p4=1 p1=0 p6=3 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 X=1,2,4,6 min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,

12、2,4,6,7, p7=3 p2=2 p4=1 p1=0 p6=3p7=3 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 X=1,2,4,6,7 min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, p5=6 p2=2 p4=1 p1=0 p6=3p7=3 p5=6 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 X=1,2,4,6,7 min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,1

13、0,11=8 X=1,2,3,4,5,6,7, p3=8 p2=2 p4=1 p1=0 p6=3p7=3 p5=6 p3=8 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 X=1,2,3,4,6,7 min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10 X=1,2,3,4,5,6,7,8, p8=10 p2=2 p4=1 p1=0 p6=3p7=3 p5=6 p3=8 p8=10 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 X=1,2,3,4,6,7,8 1 1到到8 8的最

14、短路徑為的最短路徑為11，4 4，7 7，5 5，88，長(zhǎng)度為，長(zhǎng)度為1010。 p2=2 p4=1 p1=0 p6=3p7=3 p5=6 p3=8 p8=10 課堂練習(xí)：課堂練習(xí)： 1. 用用Dijkstra算法求下圖從算法求下圖從v1到到v6的最短距離及路線(xiàn)。的最短距離及路線(xiàn)。 v3v54 v1 v2 v4 v6 3 5 2 2 2 4 2 1 v1到到v6的最短路為：的最短路為： 6521 vvvv 2. 求下圖中求下圖中v1點(diǎn)到另外任意一點(diǎn)的最短路徑點(diǎn)到另外任意一點(diǎn)的最短路徑 v1 v2 v3 v4 v6 v5 3 2 2 7 6 2 1 33 v1 V2 V3 V4 V6 V5 3

15、2 2 7 6 2 1 33 0 2 4 71 4 v1 V2 V3 V4 V6 V5 3 2 2 7 6 2 1 33 0 2 4 71 4 算法適用條件：算法適用條件： Dijkstra算法只適用于全部權(quán)為非負(fù)情況，如果某算法只適用于全部權(quán)為非負(fù)情況，如果某 邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近 算法。算法。 例例6.7 如右圖所示中按如右圖所示中按dijkstra算算 法可得法可得P(v1)=5為從為從vsv1的最短的最短 路長(zhǎng)顯然是錯(cuò)誤的，從路長(zhǎng)顯然是錯(cuò)誤的，從vsv2v1 路長(zhǎng)只有路長(zhǎng)只有3。 v2 vsv1 5 -58 例例6.8 設(shè)

16、備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初， 公司就要決定是購(gòu)買(mǎi)新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)公司就要決定是購(gòu)買(mǎi)新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu) 置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用 就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用 就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年 內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已

17、知： 設(shè)備每年年初的價(jià)格表設(shè)備每年年初的價(jià)格表 年份年份12345 年初價(jià)格年初價(jià)格1111121213 設(shè)備維修費(fèi)如下表設(shè)備維修費(fèi)如下表 使用年數(shù)使用年數(shù)0-11-22-33-44-5 每年維修費(fèi)用每年維修費(fèi)用5681118 解：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖：用解：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖：用vi表示表示“第第i年年年年 初購(gòu)進(jìn)一臺(tái)新設(shè)備初購(gòu)進(jìn)一臺(tái)新設(shè)備”,弧（?。╲i,vj）表示第）表示第i年年初購(gòu)進(jìn)的設(shè)備一年年初購(gòu)進(jìn)的設(shè)備一 直使用到第直使用到第j年年初。年年初。 v1 v2v3v4v5v6 把所有弧的權(quán)數(shù)計(jì)算如下表，把所有弧的權(quán)數(shù)計(jì)算如下表，把權(quán)數(shù)賦到圖中，再用把權(quán)數(shù)賦到圖中，再用 Dijkstra算法求最短路。算法求最短路。 123456 11622304159 216223041 3172331 41723 518 6 v1 v2v3v4v5v616 22 30 41 59 16 22 30 41 31 23 171817 23 W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6+8+11+18=59 W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30