應(yīng)用一：最短路問題

1、數(shù)學(xué)建模數(shù)學(xué)建模圖論方法專題圖論方法專題 最最 短短 路路 問問 題題 它不僅它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問題可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問題而且經(jīng)常被作為一個(gè)基本工具，用于解決而且經(jīng)常被作為一個(gè)基本工具，用于解決其它優(yōu)化問題如其它優(yōu)化問題如v定義定義：設(shè)設(shè)P(u,v)是加權(quán)圖是加權(quán)圖G中從中從u到到v的路徑的路徑,則該路則該路徑上的邊權(quán)之和稱為該路徑的權(quán)徑上的邊權(quán)之和稱為該路徑的權(quán),記為記為w(P). 從從u到到v的路徑中權(quán)最小者的路徑中權(quán)最小者 P*(u,v)稱為稱為u到到v的的.v最短路問題在實(shí)際工作中應(yīng)用最短路問題在實(shí)際工作中應(yīng)用u1、通訊網(wǎng)絡(luò)中最可靠問題、通訊網(wǎng)絡(luò)中最可

2、靠問題u2、最大容量問題、最大容量問題u3、統(tǒng)籌方法中求關(guān)鍵路線、統(tǒng)籌方法中求關(guān)鍵路線u4、背包問題、背包問題u5、選址問題、選址問題u6、工件加工順序問題、工件加工順序問題u7、中國郵遞員問題、中國郵遞員問題若若v0 v1 vm 是是G中從中從v0到到vm的最短路的最短路, 則對(duì)則對(duì)1km, v0v1 vk 必為必為G中從中從v0到到vk的最短路的最短路. 即：最短路是一條路，且最短路的任一段也是最短路。即：最短路是一條路，且最短路的任一段也是最短路。vDijkstra算法算法 Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉（Dijkstra）于）于19

3、59 年提出的。年提出的。1)尋求從一固定頂點(diǎn)尋求從一固定頂點(diǎn)v0到其余各點(diǎn)的最短路徑到其余各點(diǎn)的最短路徑;2)有向圖、無向圖和混合圖有向圖、無向圖和混合圖;3)權(quán)非負(fù)權(quán)非負(fù).：從始點(diǎn)出發(fā)，逐步從始點(diǎn)出發(fā)，逐步順序地向外探尋順序地向外探尋，每向外延伸一步都要求每向外延伸一步都要求是是 算法步驟算法步驟S: 具有永久標(biāo)號(hào)的頂點(diǎn)集具有永久標(biāo)號(hào)的頂點(diǎn)集;l(v): v的標(biāo)記的標(biāo)記,表示從起點(diǎn)表示從起點(diǎn)v0到到v的一條路的權(quán)的一條路的權(quán); z(v):v的父頂點(diǎn)的父頂點(diǎn),用以確定最短路徑用以確定最短路徑; 兩種標(biāo)號(hào)兩種標(biāo)號(hào) P 標(biāo)號(hào)標(biāo)號(hào)（Permanent固定固定/永久性標(biāo)號(hào)）永久性標(biāo)號(hào)） 從始點(diǎn)到該標(biāo)

4、號(hào)點(diǎn)的最短路權(quán)從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán) T 標(biāo)號(hào)標(biāo)號(hào)（Temporary臨時(shí)性標(biāo)號(hào)）臨時(shí)性標(biāo)號(hào)） 從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)輸入加權(quán)圖的帶權(quán)鄰接矩陣輸入加權(quán)圖的帶權(quán)鄰接矩陣w=w(vi,vj)nxn.1)初始化：令初始化：令l(v0)=0, （給起始點(diǎn)給起始點(diǎn)v0標(biāo)上固定標(biāo)號(hào)標(biāo)上固定標(biāo)號(hào)） , v v0 ,l(v)= （其余各點(diǎn)標(biāo)臨時(shí)性標(biāo)號(hào)其余各點(diǎn)標(biāo)臨時(shí)性標(biāo)號(hào) ）; S=v0; z(v)=v02)更新更新l(v), z(v) 尋找不在尋找不在S中的頂點(diǎn)中的頂點(diǎn)u（與前一點(diǎn)相鄰接）（與前一點(diǎn)相鄰接）,使使l(u)為最小為最小.把把u加入到加入到S中中,然后對(duì)所有不在然

5、后對(duì)所有不在S中的頂點(diǎn)中的頂點(diǎn)v,如如l(v)l(u)+w(u,v),則則更新更新l(v),z(v), 即即 l(v)l(u)+w(u,v),z(v)u;3)重復(fù)步驟重復(fù)步驟2), 直到所有頂點(diǎn)都在直到所有頂點(diǎn)都在S中為止中為止.例例1： 用用Dijkstra算法求下圖從算法求下圖從v1到到v6的最短路。的最短路。 v1v2v3v4v6v5352242421 解解 （1）首先給）首先給v1以以P標(biāo)號(hào)，給其余所有點(diǎn)標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。標(biāo)號(hào)。0)(1 vP)6,3,2()( ivTi（2）330,min)(, )(min)(12122 lvPvTvT550,min)(, )(min)(131

6、33 lvPvTvT23456222min ()min (), (), (), (), ()()3,()3()1jjvsT vT vT vT vT vT vT vp vz v所以有，1vS 21vvS， v1的鄰接點(diǎn)為的鄰接點(diǎn)為v2 ，v3 。v1v2v3v4v6v5352242421（4）413,5min)(, )(min)(23233 lvPvTvT523,min)(, )(min)(24244 lvPvTvT523,min)(, )(min)(25255 lvPvTvT2)(4)(, 4)()(),(),(),(min)(min3336543 vfvpvTvTvTvTvTvTjsvj，所

7、以有，所以有，例例1： 用用Dijkstra算法求下圖從算法求下圖從v1到到v6的最短路。的最短路。 v2的鄰接點(diǎn)為的鄰接點(diǎn)為v3 ，v4 ，v5 。321vvvS， v1v2v3v4v6v5352242421（5）；544,5min)(, )(min)(35355 lvPvTvT725, 45,min)(,)(, )(min)(56546466 lvPlvPvTvT（6）反向追蹤得反向追蹤得v1到到v6的最短路為：的最短路為：6521vvvv5)(, 5)(, 5)()()(),(),(min)(min5454654 vpvpvTvTvTvTvTvTjsvj所以有，所以有，5)(7)(, 7

8、)(min)(min666 vfvpvTvTjsvj，所以有，所以有，v3的鄰接點(diǎn)為的鄰接點(diǎn)為v5 。2)()(5454321 vfvfvvvvvS；，1,6例例2：v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 1, 1,11, 1, 1, 1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 1, 1,11, 1, 1, 1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,31,5v5v223464v3v1v41210 6

9、 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,31,61,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,33,53,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1,31, 3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1,31, 3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11,

10、2,61, 1,31,3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11, 2,61, 1,31,3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11, 2,65,121,35,93,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11, 2,65,121,35,9 知從知從v1到到v8 的最短路為：的最短路為： P1，8=P（v1，v3 ， v2， v5，v8）w= 0 1 2 inf 7 4 8 inf; 1 0 2 3 inf inf

11、7 inf; 2 2 0 1 5 inf inf inf; inf 3 1 0 3 inf inf 6; 7 inf 5 3 0 3 inf 4; 4 inf inf inf 3 0 2 6; 8 7 inf inf inf 2 0 4; inf inf inf 6 4 6 4 0l = 0 1 2 3 6 4 6 9z = 1 1 1 3 4 1 6 40v2v1v3v4v5v1445642537w= 0 4 1 inf inf inf; inf 0 inf 4 2 4; inf 5 0 inf 6 7; inf inf inf 0 inf inf; inf inf inf 5 0 inf;

12、 inf inf inf inf 3 0;l = 0 4 1 8 6 8 6 9z = 1 1 1 2 2 3 6 4z 使用范圍使用范圍:1)求每對(duì)頂點(diǎn)的最短路徑求每對(duì)頂點(diǎn)的最短路徑;2)有向圖、無向圖和混合圖有向圖、無向圖和混合圖;z 算法思想算法思想: 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次遞推直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次遞推地構(gòu)造出地構(gòu)造出n個(gè)矩陣個(gè)矩陣D(1), D(2), , D(v), D(v)是圖的距離矩陣是圖的距離矩陣, 同時(shí)引入一個(gè)后繼點(diǎn)矩陣記錄兩點(diǎn)間的最短路徑同時(shí)引入一個(gè)后繼點(diǎn)矩陣記錄兩點(diǎn)間的最短路徑.z 輸入?yún)?shù)：輸入?yún)?shù)：G的帶權(quán)鄰接矩陣的帶權(quán)鄰

13、接矩陣W.z 算法輸出：距離矩陣算法輸出：距離矩陣D以及路由矩陣以及路由矩陣R.（I）求距離矩陣的方法）求距離矩陣的方法.（II）求路徑矩陣的方法）求路徑矩陣的方法.在建立距離矩陣的同時(shí)可建立路徑矩陣在建立距離矩陣的同時(shí)可建立路徑矩陣R ivjv（III）查找最短路路徑的方法）查找最短路路徑的方法.然后用同樣的方法再分頭查找若：然后用同樣的方法再分頭查找若：1av2av3avkav1bv2bvmbv（IV）Floyd算法：求任意兩頂點(diǎn)間的最短路算法：求任意兩頂點(diǎn)間的最短路.例例3： 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑. ,053142503330212

14、044401210 )0(D,654321654321654321654321654321654321 )0(R,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入點(diǎn)插入點(diǎn) v1，得：得：,053132503330212043401210)1(D,654311654321654321654321154321654321 )1(R矩陣中帶矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素的項(xiàng)為經(jīng)迭代比較以后有變化的元素.,min) 1() 1() 1()(kkjkikkijkijdddd插入點(diǎn)插入點(diǎn) v2，得：得：,05

15、3132503330212043401210)1(D矩陣中帶矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素的項(xiàng)為經(jīng)迭代比較以后有變化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入點(diǎn)插入點(diǎn) v3，得：得：,05313250333021204534012510)2(D,

16、min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D插入點(diǎn)插入點(diǎn) v4，得：得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221 )4(R,)4()5(DD插入點(diǎn)插入點(diǎn) v5，得：得：,)4()5(RR,min) 1() 1() 1()(kkjkikkijkijdddd插入點(diǎn)插入點(diǎn) v6，得：得：,05313250359103302671520453964012107510)5(D,053132503

17、587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R8)6(52d8)6(52d故從故從v5到到v2的最短路為的最短路為8 6)6(52R由由v6向向v5追溯追溯: . 6)6(56R由由v6向向v2追溯追溯: , 1)6(62R. 2)6(12R所以從到的最短路徑為：所以從到的最短路徑為： .2165vvvva=0 1 inf inf

18、inf 2; 1 0 4 inf inf 4; inf 4 0 2 inf 1; inf inf 2 0 3 3; inf inf inf 3 0 5; 2 4 1 3 5 0;1v3v2v4v5v68523374a=0 8 6 2 inf; inf 0 -5 -3 inf; inf inf 0 inf 4; inf inf inf 0 inf; inf 3 inf 7 0; 最最 短短 路路 應(yīng)用應(yīng)用 例：某企業(yè)使用一種設(shè)備，在每年年初，決策者需要決定是否例：某企業(yè)使用一種設(shè)備，在每年年初，決策者需要決定是否購置新的，還是繼續(xù)使用舊的。若購置新設(shè)備，就要支付一定購置新的，還是繼續(xù)使用舊的。若

19、購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用舊的，需要支付一定的維修費(fèi)用?，F(xiàn)的購置費(fèi)用；若繼續(xù)使用舊的，需要支付一定的維修費(fèi)用。現(xiàn)在的問題是如何制定一個(gè)五年計(jì)劃，使總的支付費(fèi)用最少，表在的問題是如何制定一個(gè)五年計(jì)劃，使總的支付費(fèi)用最少，表1為設(shè)備在各年年初的價(jià)格，表為設(shè)備在各年年初的價(jià)格，表2為使用不同時(shí)間的設(shè)備所需要的為使用不同時(shí)間的設(shè)備所需要的維修費(fèi)用。維修費(fèi)用。表表1 設(shè)備的各年價(jià)格設(shè)備的各年價(jià)格表表2 使用不同時(shí)間的維修費(fèi)用使用不同時(shí)間的維修費(fèi)用年份年份 一一 二二 三三 四四 五五購 置 費(fèi)購 置 費(fèi) 11 11 12 12 13使用年限使用年限 01 12 23 34 45年修理

20、費(fèi)年修理費(fèi) 5 6 8 11 18解：（解：（1）分析：顯然可以選擇的設(shè)備更新方案是很多的。例）分析：顯然可以選擇的設(shè)備更新方案是很多的。例如每年都更新一臺(tái)新設(shè)備，其購置費(fèi)用為（如每年都更新一臺(tái)新設(shè)備，其購置費(fèi)用為（11+11+12+12+13）萬元萬元=59萬元，而每年支付的維修費(fèi)用為萬元，而每年支付的維修費(fèi)用為5萬元，五年的合計(jì)萬元，五年的合計(jì)為為25萬元，于是五年的支付費(fèi)用為（萬元，于是五年的支付費(fèi)用為（59+25）=84萬元。萬元。 又如可決定在第一，三，五年各購置一臺(tái)，這個(gè)方案的設(shè)又如可決定在第一，三，五年各購置一臺(tái)，這個(gè)方案的設(shè)備購置費(fèi)用為（備購置費(fèi)用為（11+12+13）=36萬

21、元，維修費(fèi)用為萬元，維修費(fèi)用為（5+6+5+6+5）=27萬元，五年總費(fèi)用為萬元，五年總費(fèi)用為63萬元。萬元。 如何制定計(jì)劃適得總的支付費(fèi)用最少呢？可以把此問題如何制定計(jì)劃適得總的支付費(fèi)用最少呢？可以把此問題最化為最短路問題。最化為最短路問題。 （2）用點(diǎn)）用點(diǎn)v vi i 代表代表“第第i年年初購進(jìn)一臺(tái)新設(shè)備年年初購進(jìn)一臺(tái)新設(shè)備”這種狀態(tài)（這種狀態(tài)（v v6為第為第5年年年年底的末狀態(tài)）?；〉椎哪顟B(tài)）?；。╲ vi i ,v vj j） 表示第表示第i年年初購進(jìn)的設(shè)備一直使用到第年年初購進(jìn)的設(shè)備一直使用到第j年年年年初?；。ǔ?。?。╲i ,vj）上的權(quán)數(shù)表示該期間設(shè)備所需的費(fèi)用）上的權(quán)數(shù)表

22、示該期間設(shè)備所需的費(fèi)用. 每條弧的權(quán)可按已知資料計(jì)算出來。如（每條弧的權(quán)可按已知資料計(jì)算出來。如（v v1，v v4）是第一年年初購進(jìn)的）是第一年年初購進(jìn)的一臺(tái)設(shè)備（支付購置費(fèi)用為本一臺(tái)設(shè)備（支付購置費(fèi)用為本11萬元），一直使用到了第萬元），一直使用到了第3年年底（支付年年底（支付維修費(fèi)用為維修費(fèi)用為5+6+8=19萬元），故?。ㄈf元），故?。╲ v1，v v4）權(quán)重為）權(quán)重為30萬元。萬元。 這樣一來，制定一個(gè)最優(yōu)更新計(jì)劃的問題就等價(jià)于尋求從這樣一來，制定一個(gè)最優(yōu)更新計(jì)劃的問題就等價(jià)于尋求從V1到到V6的最的最短路問題。短路問題。 按求最短路的計(jì)算方法（按求最短路的計(jì)算方法（V1，V3，V6

23、）及（）及（V1，V4，V6）均為最短路）均為最短路線，權(quán)重為線，權(quán)重為53萬元。萬元。v1v2v3v4 v5 v61616171718223041592230412331231、中心問題、中心問題所謂中心選址問題就是在一網(wǎng)絡(luò)中選擇一所謂中心選址問題就是在一網(wǎng)絡(luò)中選擇一點(diǎn)，建立點(diǎn)，建立公用服務(wù)設(shè)施公用服務(wù)設(shè)施，為該網(wǎng)絡(luò)中的點(diǎn)，為該網(wǎng)絡(luò)中的點(diǎn)提供服務(wù)，使得服務(wù)效率最高。比如一個(gè)提供服務(wù)，使得服務(wù)效率最高。比如一個(gè)區(qū)域的消防站、自來水廠、學(xué)校、變電站、區(qū)域的消防站、自來水廠、學(xué)校、變電站、銀行、商店等選址。為了提高服務(wù)效率，銀行、商店等選址。為了提高服務(wù)效率，自然的想法是將這些設(shè)施建立在中心地點(diǎn)。

24、自然的想法是將這些設(shè)施建立在中心地點(diǎn)。要求要求網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點(diǎn)離服務(wù)設(shè)施的網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點(diǎn)離服務(wù)設(shè)施的距離盡可能小距離盡可能小。ijnjidMaxvd 1)()(1inivdMinI Ivdk )(), 2 , 1()(1nidvhnjiji )()(1inikvhMinvh 設(shè)網(wǎng)絡(luò)設(shè)網(wǎng)絡(luò)N有個(gè)有個(gè)n點(diǎn)點(diǎn)v1,v2,vn。dij表示點(diǎn)表示點(diǎn)vi到到vj之間的距之間的距離（即最短路的長度），并記離（即最短路的長度），并記dii=0(i=1,2,n)。定義定義1: 記記 , 。若。若 ,則稱點(diǎn)則稱點(diǎn)vk為網(wǎng)絡(luò)為網(wǎng)絡(luò)N的中心，的中心，I為直徑。為直徑。定義定義2: 令令 ，若，若 ，則稱，則

25、稱vk為網(wǎng)絡(luò)為網(wǎng)絡(luò)N的中心。的中心。例例1某城市要建立一個(gè)消防站，為該市所某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示問應(yīng)設(shè)在哪個(gè)屬的七個(gè)區(qū)服務(wù)，如圖所示問應(yīng)設(shè)在哪個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最 距離矩陣第距離矩陣第i行的最大值行的最大值05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6

26、,故應(yīng)將消防站設(shè)在v3處. 例例2 教育部門打算在某新建城區(qū)建一所學(xué)教育部門打算在某新建城區(qū)建一所學(xué)校，讓附近七個(gè)居民區(qū)的學(xué)生就近入學(xué)。校，讓附近七個(gè)居民區(qū)的學(xué)生就近入學(xué)。七個(gè)居民區(qū)之間的道路如下圖所示，學(xué)校七個(gè)居民區(qū)之間的道路如下圖所示，學(xué)校應(yīng)建在哪個(gè)居民區(qū)，才能使大家都方便？應(yīng)建在哪個(gè)居民區(qū)，才能使大家都方便？（圖中距離單位：百米）。（圖中距離單位：百米）。2、重心問題、重心問題例例3 例例2中，七個(gè)居民區(qū)的學(xué)生人數(shù)分別為：中，七個(gè)居民區(qū)的學(xué)生人數(shù)分別為：40、25、45、30、20、35、50人，學(xué)校應(yīng)人，學(xué)校應(yīng)建在哪個(gè)居民區(qū)，才能使大家都方便？建在哪個(gè)居民區(qū)，才能使大家都方便？（圖中距

27、離單位：百米）。（圖中距離單位：百米）。某合同戰(zhàn)術(shù)訓(xùn)練基地為保障即將進(jìn)行的聯(lián)合軍事演某合同戰(zhàn)術(shù)訓(xùn)練基地為保障即將進(jìn)行的聯(lián)合軍事演習(xí)，準(zhǔn)備在原有的習(xí)，準(zhǔn)備在原有的1個(gè)油庫的基礎(chǔ)上，再設(shè)立個(gè)油庫的基礎(chǔ)上，再設(shè)立7個(gè)固個(gè)固定的燃料補(bǔ)給點(diǎn)。定的燃料補(bǔ)給點(diǎn)。v1v7v6v2v8v5v3v4油庫與補(bǔ)給點(diǎn)的位置如圖所示，其中油庫位于油庫與補(bǔ)給點(diǎn)的位置如圖所示，其中油庫位于v1點(diǎn)，點(diǎn)，補(bǔ)給點(diǎn)位于補(bǔ)給點(diǎn)位于v2, , v8點(diǎn)。點(diǎn)。經(jīng)過前期的測(cè)繪工作，如果在油庫和補(bǔ)給點(diǎn)之間修建經(jīng)過前期的測(cè)繪工作，如果在油庫和補(bǔ)給點(diǎn)之間修建簡易公路，由于地形不同，每段公路花費(fèi)如圖，每單簡易公路，由于地形不同，每段公路花費(fèi)如圖，每單

28、位費(fèi)用為位費(fèi)用為1萬元。請(qǐng)根據(jù)測(cè)繪結(jié)果，規(guī)劃一個(gè)總造價(jià)萬元。請(qǐng)根據(jù)測(cè)繪結(jié)果，規(guī)劃一個(gè)總造價(jià)最低的建設(shè)方案。最低的建設(shè)方案。v1v7v6v2v8v5v3v425734326436174182總造價(jià)最低總造價(jià)最低各補(bǔ)給點(diǎn)到油庫的各補(bǔ)給點(diǎn)到油庫的花費(fèi)均達(dá)到最小花費(fèi)均達(dá)到最??？v1v7 6v6 4 4v2 1 1v8 9v5 6v3 2 2 v4 32243611簡易公路建設(shè)方案簡易公路建設(shè)方案如圖的交通網(wǎng)絡(luò)，每條弧上的數(shù)字代表車輛在該路段行駛所需如圖的交通網(wǎng)絡(luò)，每條弧上的數(shù)字代表車輛在該路段行駛所需的時(shí)間，有向邊表示單行道，無向邊表示可雙向行駛。若有一的時(shí)間，有向邊表示單行道，無向邊表示可雙向行駛。

29、若有一批貨物要從批貨物要從1號(hào)頂點(diǎn)運(yùn)往號(hào)頂點(diǎn)運(yùn)往11號(hào)頂點(diǎn)，問運(yùn)貨車應(yīng)沿哪條線路行駛，號(hào)頂點(diǎn)，問運(yùn)貨車應(yīng)沿哪條線路行駛，才能最快地到達(dá)目的地？才能最快地到達(dá)目的地？ 102374116598118 9 10 11某公司在六個(gè)城市某公司在六個(gè)城市c1, ,c6中有分公司，從中有分公司，從ci到到cj的直接航程票價(jià)記在下述矩陣中的的直接航程票價(jià)記在下述矩陣中的 (i,j) 位置上。（位置上。（表示無直接航路），請(qǐng)幫助該公司設(shè)計(jì)一張任意兩城表示無直接航路），請(qǐng)幫助該公司設(shè)計(jì)一張任意兩城市間的票價(jià)最便宜的路線表。市間的票價(jià)最便宜的路線表。 055252510550102025251001020402010015252015050102540500已知一個(gè)地區(qū)的交通網(wǎng)絡(luò)如下：其中