第8講 最短路問(wèn)題

1、數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 最短路問(wèn)題最短路問(wèn)題實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容2、會(huì)用、會(huì)用Matlab軟件求最短路軟件求最短路1、了解最短路的算法及其應(yīng)用、了解最短路的算法及其應(yīng)用1、圖、圖 論論 的的 基基 本本 概概 念念2、最、最 短短 路路 問(wèn)問(wèn) 題題 及及 其其 算算 法法3、最、最 短短 路路 的的 應(yīng)應(yīng) 用用4、建模案例：最優(yōu)截?cái)嗲懈顔?wèn)題、建模案例：最優(yōu)截?cái)嗲懈顔?wèn)題5、實(shí)驗(yàn)作業(yè)、實(shí)驗(yàn)作業(yè)圖圖 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的 概概 念念1、圖的定義、圖的定義2、頂點(diǎn)的次數(shù)、頂點(diǎn)的次數(shù) 3、子圖、子圖二、二、 圖圖 的的 矩矩 陣陣 表表 示示1

2、、 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣2、 鄰接矩陣鄰接矩陣返回返回定義定義有序三元組G=(V,E, )稱為一個(gè)圖圖.1 V=,21nvvv是有窮非空集，稱為頂頂點(diǎn)點(diǎn)集集， 其中的元素叫圖 G 的頂頂點(diǎn)點(diǎn).2 E 稱為邊邊集集，其中的元素叫圖 G 的邊邊.3 是從邊集 E 到頂點(diǎn)集 V 中的有序或無(wú)序的元素 偶對(duì)的集合的映射，稱為關(guān)關(guān)聯(lián)聯(lián)函函數(shù)數(shù).例例1 設(shè) G=(V ,E,)，其中 V=v1 ,v2 , v3 , v4， E=e1, e2 , e3, e4, e5,335414413312211)(,)(,)(,)(,)(vvevvevvevvevve.G 的圖解如圖.圖的定義圖的定義定義定義在圖 G 中，與

3、 V 中的有序偶(vi， vj)對(duì)應(yīng)的邊 e，稱為圖的有有向向邊邊（或?。?，而與 V 中頂點(diǎn)的無(wú)序偶 vivj相對(duì)應(yīng)的邊 e，稱為圖的無(wú)無(wú)向向邊邊.每一條邊都是無(wú)向邊的圖，叫無(wú)無(wú)向向圖圖；每一條邊都是有向邊的圖，稱為有有向向圖圖；既有無(wú)向邊又有有向邊的圖稱為混混合合圖圖.定義定義若將圖 G 的每一條邊 e 都對(duì)應(yīng)一個(gè)實(shí)數(shù) w(e)，稱 w(e)為邊的權(quán)權(quán)，并稱圖 G 為賦賦權(quán)權(quán)圖圖.規(guī)定用記號(hào)和分別表示圖的頂點(diǎn)數(shù)和邊數(shù).常用術(shù)語(yǔ)：（） 端點(diǎn)相同的邊稱為環(huán)環(huán)（） 若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊重邊（） 有邊聯(lián)結(jié)的兩個(gè)頂點(diǎn)稱為相鄰的頂點(diǎn)相鄰的頂點(diǎn)，有一個(gè)公共端點(diǎn)的邊 稱為相鄰

4、的邊相鄰的邊（） 邊和它的端點(diǎn)稱為互相關(guān)聯(lián)關(guān)聯(lián)的 （） 既沒(méi)有環(huán)也沒(méi)有平行邊的圖，稱為簡(jiǎn)單圖簡(jiǎn)單圖（） 任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖，稱為完備圖完備圖，記為 Kn，其中 n 為頂點(diǎn)的數(shù)目( 7)若 V=XY，XY=，X 中任兩頂點(diǎn)不相鄰，Y 中任兩頂點(diǎn)不相鄰，稱 G 為二元圖二元圖；若 X 中每一頂點(diǎn)皆與 Y 中一切頂點(diǎn)相鄰，稱為完備二元圖完備二元圖，記為 Km,n，其中 m,n 分別為 X 與 Y 的頂點(diǎn)數(shù)目返回返回頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù)定定義義（）在無(wú)向圖中，與頂點(diǎn) v 關(guān)聯(lián)的邊的數(shù)目（環(huán)算兩次）稱為 v的次次數(shù)數(shù)，記為 d(v)（）在有向圖中，從頂點(diǎn) v 引出的邊的數(shù)目稱為 v的出出度度，記為

5、 d+(v)，從頂點(diǎn) v引入的邊的數(shù)目稱為的入入度度，記為 d-(v)，d(v)=d+(v)+d-(v)稱為 v的次數(shù)4)(4vd5)(3)(2)(444vdvdvd定理定理)(2)()(GvdGVv推論推論任何圖中奇次頂點(diǎn)的總數(shù)必為偶數(shù)例例 在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。返回返回子圖子圖定定義義設(shè)圖 G=(V,E,),G1=(V1,E1,1)(1) 若 V1V，E1E,且當(dāng) eE1時(shí)，1(e)= (e),則稱 G1是 G 的子子圖圖特別的，若 V1=V，則 G1稱為 G 的生生成成子子圖圖(2) 設(shè) V1V，且 V1，以 V1為頂點(diǎn)集、兩個(gè)端點(diǎn)都在 V1中的圖 G 的邊為邊集的

6、圖 G 的子圖，稱為 G 的由由 V1導(dǎo)導(dǎo)出出的的子子圖圖，記為 GV1.(3)設(shè) E1E,且 E1,以 E1為邊集,E1的端點(diǎn)集為頂點(diǎn)集的圖 G 的子圖,稱為 G 的由由 E1導(dǎo)導(dǎo)出出的的子子圖圖,記為 GE1. GGv1,v4,v5Ge1,e2,e3返回返回關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣對(duì)無(wú)向圖，其關(guān)聯(lián)矩陣)(ijm，其中：不關(guān)聯(lián)與若相關(guān)聯(lián)與若jijiijevevm01M=43215432110110011000101110001vvvveeeee對(duì)有向圖，其關(guān)聯(lián)矩陣)(ijm，其中：不關(guān)聯(lián)與若的終點(diǎn)是若的起點(diǎn)是若jijijiijevevevm011注：假設(shè)圖為簡(jiǎn)單圖返回返回鄰接矩陣鄰接矩陣對(duì)無(wú)向圖，其

7、鄰接矩陣)(ijaA，其中：不相鄰與若相鄰與若jijiijvvvva01注：假設(shè)圖為簡(jiǎn)單圖A=432143210111101011011010vvvvvvvv對(duì)有向圖（，） ，其鄰接矩陣)(ijaA，其中：EvvEvvajijiij），若（），若（01對(duì)有向賦權(quán)圖，其鄰接矩陣)(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若為其權(quán)且若無(wú)向賦權(quán)圖的鄰接矩陣可類似定義A=4321432105375083802720vvvvvvvv返回返回最最 短短 路路 問(wèn)問(wèn) 題題 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短

8、短 路路三、每三、每 對(duì)對(duì) 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路返回返回基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路徑4521141vevevPvv定義定義在無(wú)向圖 G=(V,E,)中：（） 頂點(diǎn)與邊相互交錯(cuò)且iiivve1)( (i=1,2,k)的有限非空序列)(12110kkkvevevevw稱為一條從0v到kv的通路通路，記為kvvW0（）邊不重復(fù)但頂點(diǎn)可重復(fù)的通路稱為道路道路，記為kvvT0（）邊與頂點(diǎn)均不重復(fù)的通路稱為路徑路徑，記為kvvP0定義定義（）任意兩點(diǎn)均有路徑的圖稱為連通圖連通

9、圖（）起點(diǎn)與終點(diǎn)重合的路徑稱為圈圈（）連通而無(wú)圈的圖稱為樹(shù)樹(shù)定定義義（）設(shè) P(u,v)是賦權(quán)圖 G 中從 u 到 v的路徑， 則稱)()()(PEeewPw為路徑 P 的權(quán)權(quán)(2) 在賦權(quán)圖 G 中，從頂點(diǎn) u 到頂點(diǎn) v的具有最小權(quán)的路 ),(*vuP，稱為 u 到 v的最最短短路路返回返回固固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹(shù) 因此, 可采用樹(shù)生長(zhǎng)的過(guò)程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路設(shè) G 為賦權(quán)有向圖或無(wú)向圖，G 邊上的權(quán)均非負(fù)對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)

10、標(biāo)記（l v( )，z v( )） ，其中: l v( )：表從頂點(diǎn) u0到 v 的一條路的權(quán) z v( )：v 的父親點(diǎn)，用以確定最短路的路線算法的過(guò)程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終l v( )為從頂點(diǎn)u0到 v 的最短路的權(quán)S：具有永久標(biāo)號(hào)的頂點(diǎn)集輸入: G 的帶權(quán)鄰接矩陣),(vuw算法步驟：算法步驟：（4） 若S ，轉(zhuǎn) 2，否則，停止. 用上述算法求出的l v( )就是u0到v的最短路的權(quán)，從v的父親標(biāo)記)(vz追溯到u0, 就得到u0到v的最短路的路線.例例 求下圖從頂點(diǎn) u1到其余頂點(diǎn)的最短路 TO MATLAB(road1)(iul迭代次數(shù)1u2u3u 4u5u6u 7u 8

11、u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12 12最后標(biāo)記:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u)(iul1u2u3u 4u5u6u 7u 8u最后標(biāo)記:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8返回返回每每 對(duì)對(duì) 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路(二二)算算法法原原理理1、求距離矩陣的方法、求距離矩陣的方法2、求路徑矩陣的方法、求路徑矩陣的方法3、查找最短路路徑的方法、查找最短路路徑

12、的方法（一）算法的基本思想（一）算法的基本思想（三）算法步驟（三）算法步驟返回返回算法的基本思想算法的基本思想 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次構(gòu)造出個(gè)矩陣 D(1)、 D(2)、 、D()，使最后得到的矩陣 D()成為圖的距離矩陣，同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑返回返回算法原理算法原理 求距離矩陣的方法求距離矩陣的方法把帶權(quán)鄰接矩陣 W 作為距離矩陣的初值，即 D(0)=)()0(ijd=W（）D(1)= )() 1 (ijd，其中)0(1)0() 1 (,miniijijddd)0(1jd)1(ijd是從 vi到 vj的只允許以 v1作為中間點(diǎn)的路徑中最短路的長(zhǎng)度

13、（2）D(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是從 vi到 vj的只允許以 v1 、 v2作為中間點(diǎn)的路徑中最短路的長(zhǎng)度（）D()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是從 vi到 vj的只允許以 v1、v2、v作為中間點(diǎn)的路徑中最短路的長(zhǎng)度即是從 vi到 vj中間可插入任何頂點(diǎn)的路徑中最短路的長(zhǎng)，因此D()即是距離矩陣返回返回算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法R=)(ijr, rij的含義是從 vi到 vj的最短路要經(jīng)過(guò)點(diǎn)號(hào)為 rij的點(diǎn))()0()0(i

14、jrR, jrij)0(每求得一個(gè) D(k)時(shí)，按下列方式產(chǎn)生相應(yīng)的新的 R(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距離矩陣的同時(shí)可建立路徑矩陣R 即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求 時(shí)求得 ，可由 來(lái)查找任何點(diǎn)對(duì)之間最短路的路徑)(D)(R)(R返回返回ij算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點(diǎn) p1是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn).然后用同樣的方法再分頭查找若：（） 向點(diǎn) i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向點(diǎn) j 追朔得：1)(1

15、qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：jqqqpppimk,21, 12返回返回算法步驟算法步驟Floyd 算法：算法：求任意兩點(diǎn)間的最短路D(i,j)：i 到 j 的距離R(i,j)：i 到 j 之間的插入點(diǎn)輸入: 帶權(quán)鄰接矩陣 w(i,j)（） 賦初值：對(duì)所有 i,j, d(i,j)w(i,j), r(i,j)j, k1(2) 更新 d(i,j), r(i,j)對(duì)所有 i,j，若 d(i,k)+d(k,j)d(i,j)，則 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否則 kk+1，轉(zhuǎn)（） 例例

16、 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑 TO MATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故從 v5到 v1的最短路為51r由 v4向 v5追朔：3, 35354rr;由 v4向 v1追朔：141r所以從 v5到 v1的最短路徑為：1435.返回返回最最 短短 路路 的的 應(yīng)應(yīng) 用用一、一、 可化為最短路問(wèn)題的多階段決策問(wèn)題可化為最短路問(wèn)題的多階段決策問(wèn)題二、二、 選選 址址 問(wèn)問(wèn) 題題1、 中心問(wèn)題中心問(wèn)題2、 重心問(wèn)題重心問(wèn)題返回返回可化為最短路問(wèn)題的多階段決策問(wèn)題可化為最短路問(wèn)

17、題的多階段決策問(wèn)題 例例 1 設(shè)備更新問(wèn)題：企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購(gòu)置新的，還是繼續(xù)使用舊的.若購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)用；若繼續(xù)使用，則需支付一定的維修費(fèi)用.現(xiàn)要制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使得五年內(nèi)總的支付費(fèi)用最少. 已知該種設(shè)備在每年年初的價(jià)格為：第一年第二年第三年第四年第五年1111121213 使用不同時(shí)間設(shè)備所需維修費(fèi)為：使用年限0112233445維修費(fèi)5681118構(gòu)造加權(quán)有向圖 G1(V,E)（1）頂點(diǎn)集 VXib , i=1,2,3,4,5Xirk( ), i=2,3,4,5,6; k=1,2,i-1,每個(gè)頂點(diǎn)代表年初的一種決策，其中頂點(diǎn)

18、Xib代表第 i 年初購(gòu)置新設(shè)備的決策，頂點(diǎn)Xirk( )代表第 i 年初修理用過(guò) k 年的舊設(shè)備的決策（2）弧集 E=(,),(,),(),XXXXibibirkib11i=1,2,3,4; k=1,2,i-1 (,),( )XXibir11, i=1,2,3,4,5(,)(),()XXirkirk11,i=1,2,3,4,5;k=1,2,i-1若第 i 年初作了決策Xi后，第 i+1 年初可以作決策Xi1，則頂點(diǎn)Xi與Xi1之間有弧(Xi,Xi1)，其權(quán) W(Xi,Xi1)代表第 i 年初到第 i+1 年初之間的費(fèi) 用.例如，弧(,)( )XXbr341代表第 3 年初買(mǎi)新設(shè) 備，第四 年

19、初決定用第三 年買(mǎi)的用 過(guò)一年的 舊設(shè)備， 其權(quán)則為 第三年初 的購(gòu)置費(fèi) 與三、四年間 的維修費(fèi) 之和，為 12517（3）問(wèn)題轉(zhuǎn)化為頂點(diǎn)Xb1到Xrk6( )的最短路問(wèn)題.五年的最優(yōu)購(gòu)置費(fèi)為 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )為頂點(diǎn)Xb1到Xrk6( )的最短路的權(quán).求 得 最 短 路 的 權(quán) 為 53， 而 兩 條 最 短 路 分 別 為 XXXXXXbrrbrr1213245162( )()( )();XXXXXXbrbrrr1213415263( )( )()()因 此 ， 計(jì) 劃 為 第 一 、 三 年 初 購(gòu) 置

20、 新 設(shè) 備 ， 或 第 一 、 四 年 初 購(gòu) 置 新 設(shè) 備 ，五 年 費(fèi) 用 均 最 省 ， 為 53.也可構(gòu)造加權(quán)有向圖 G2(V,E).（1）頂點(diǎn)集 V=V V V V V V123456,，Vi表第 i 年初購(gòu)置新設(shè)備的決策，V6表第五年底.（2）弧集 E=(,)V Vij，i=1,2,3,4,5; ij6,弧(,)V Vij表第 i 年初購(gòu)進(jìn)一臺(tái)設(shè)備一直使用到第 j 年初的決策，其權(quán) W(,)V Vij表由這一決策在第 i 年初到第 j 年初的總費(fèi)用，如W(,)V V14=11+5+6+8=30.（3）問(wèn)題轉(zhuǎn)化為求V1到V6的最短路問(wèn)題，求得兩條最短路為VVV146，VVV136

21、，權(quán)為 53，與圖 G1(V,E)的解相同返回返回（2） 計(jì)算在各點(diǎn)iv設(shè)立服務(wù)設(shè)施的最大服務(wù)距離)(ivS max)(1ijjidvS , 2 , 1i 選址問(wèn)題選址問(wèn)題-中心問(wèn)題中心問(wèn)題例例 2某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示問(wèn)應(yīng)設(shè)在那個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短（1）用 Floyd 算法求出距離矩陣 D=)(ijd（3）求出頂點(diǎn)kv，使)(min)(1iikvSvS則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱為圖的中心點(diǎn)中心點(diǎn) TO MATLAB(road3(floyd)05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730