第8講 最短路問題ppt課件

1、1數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 最短路問題最短路問題2實(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、最、最 短短 路路 問問 題題 及及 其其 算算 法法3、最、最 短短 路路 的的 應(yīng)應(yīng) 用用4、建模案例：最優(yōu)截?cái)嗲懈顔栴}、建模案例：最優(yōu)截?cái)嗲懈顔栴}5、實(shí)驗(yàn)作業(yè)、實(shí)驗(yàn)作業(yè)3圖圖 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的 概概 念念1、圖的定義、圖的定義2、頂點(diǎn)的次數(shù)、頂點(diǎn)的次數(shù) 3、子圖、子圖二、二、 圖圖 的的 矩矩 陣陣 表表

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

3、G 中，與 V 中的有序偶(vi， vj)對應(yīng)的邊 e，稱為圖的有有向向邊邊（或?。?，而與 V 中頂點(diǎn)的無序偶 vivj相對應(yīng)的邊 e，稱為圖的無無向向邊邊.每一條邊都是無向邊的圖，叫無無向向圖圖；每一條邊都是有向邊的圖，稱為有有向向圖圖；既有無向邊又有有向邊的圖稱為混混合合圖圖.定義定義若將圖 G 的每一條邊 e 都對應(yīng)一個(gè)實(shí)數(shù) w(e)，稱 w(e)為邊的權(quán)權(quán)，并稱圖 G 為賦賦權(quán)權(quán)圖圖.規(guī)定用記號和分別表示圖的頂點(diǎn)數(shù)和邊數(shù).6常用術(shù)語：（） 端點(diǎn)相同的邊稱為環(huán)環(huán)（） 若一對頂點(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)的 （） 既沒有環(huán)也沒有平行邊的圖，稱為簡單圖簡單圖（） 任意兩頂點(diǎ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ù)目7返回返回8頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù)定定義義（）在無向圖中，與頂點(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)(444vdvdvd9定定理理)(2)()(GvdGVv推推論論任何圖中奇次頂點(diǎn)的總數(shù)必為偶數(shù)例例 在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。返回返回10子圖子圖定定義義設(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中

6、的圖 G 的邊為邊集的圖 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返回返回11關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣對無向圖，其關(guān)聯(lián)矩陣)(ijm，其中：不關(guān)聯(lián)與若相關(guān)聯(lián)與若jijiijevevm01M=43215432110110011000101110001vvvveeeee對有向圖，其關(guān)聯(lián)矩陣)(ijm，其中：不關(guān)聯(lián)與若的終點(diǎn)是若的起點(diǎn)是若jijijiijevevevm011注：假設(shè)圖為簡單圖返回返回1

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

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

9、定定義義（）任意兩點(diǎn)均有路徑的圖稱為連連通通圖圖（）起點(diǎn)與終點(diǎn)重合的路徑稱為圈圈（）連通而無圈的圖稱為樹樹定定義義（）設(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 的最最短短路路返回返回17固固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹 因此, 可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路18設(shè) G

10、為賦權(quán)有向圖或無向圖，G 邊上的權(quán)均非負(fù)對每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（l v( )，z v( )） ，其中: l v( )：表從頂點(diǎn) u0到 v 的一條路的權(quán) z v( )：v 的父親點(diǎn)，用以確定最短路的路線算法的過程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終l v( )為從頂點(diǎn)u0到 v 的最短路的權(quán)S：具有永久標(biāo)號的頂點(diǎn)集輸入: G 的帶權(quán)鄰接矩陣),(vuw19算法步驟：算法步驟：（4） 若S ，轉(zhuǎn) 2，否則，停止. 用上述算法求出的l v( )就是u0到v的最短路的權(quán)，從v的父親標(biāo)記)(vz追溯到u0, 就得到u0到v的最短路的路線.20例例 求下圖從頂點(diǎn)u1到其余頂點(diǎn)的最短路 TO MATLAB

11、(road1)21)(iul迭代次數(shù)1u2u3u 4u5u6u 7u 8u2345678 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 5u22)(iul1u2u3u 4u5u6u 7u 8u最后標(biāo)記:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8返回返回23每每 對對 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路(二二)算算法法原原理理1、求距離矩陣的方法、求距離矩陣的方

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

13、0(1jd)1 (ijd是從 vi到 vj的只允許以 v1作為中間點(diǎn)的路徑中最短路的長度（2）D(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是從 vi到 vj的只允許以 v1 、 v2作為中間點(diǎn)的路徑中最短路的長度（）D()=)()(ijd，其中)1()1()(,miniijijddd) 1( jd)(ijd是從 vi到 vj的只允許以 v1、v2、v作為中間點(diǎn)的路徑中最短路的長度即是從 vi到 vj中間可插入任何頂點(diǎn)的路徑中最短路的長，因此D()即是距離矩陣返回返回26算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法R=

14、)(ijr, rij的含義是從 vi到 vj的最短路要經(jīng)過點(diǎn)號為 rij的點(diǎn))()0()0(ijrR, 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í)求得 ，可由 來查找任何點(diǎn)對之間最短路的路徑)(D)(R)(R返回返回27ij算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點(diǎn) p1是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn).然后用同樣的方法再分頭查找若：（） 向點(diǎn)

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

16、j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否則 kk+1，轉(zhuǎn)（） 29例例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑 TO MATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故從v5到v1的最短路為51r由 v4向 v5追朔：3, 35354rr;由 v4向 v1追朔：141r所以從 v5到 v1的最短路徑為：1435.返回返回30最最 短短 路路 的的 應(yīng)應(yīng) 用用一、一、 可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題二、二、 選選 址址 問問

17、題題1、 中心問題中心問題2、 重心問題重心問題返回返回31可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題 例例 1 設(shè)備更新問題：企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設(shè)備，就要支付一定的購置費(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)568111832構(gòu)造加權(quán)有向圖 G1(V,E)（1）頂點(diǎn)集 VXib , i=1,2,

18、3,4,5Xirk( ), i=2,3,4,5,6; k=1,2,i-1,每個(gè)頂點(diǎn)代表年初的一種決策，其中頂點(diǎn)Xib代表第 i 年初購置新設(shè)備的決策，頂點(diǎn)Xirk( )代表第 i 年初修理用過 k 年的舊設(shè)備的決策33（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)代表

19、第 i 年初到第 i+1 年初之間的費(fèi) 用.例如，弧(,)( )XXbr341代表第 3 年初買新設(shè) 備，第四 年初決定用第三 年買的用 過一年的 舊設(shè)備， 其權(quán)則為 第三年初 的購置費(fèi) 與三、四年間 的維修費(fèi) 之和，為 12517（3）問題轉(zhuǎn)化為頂點(diǎn)Xb1到Xrk6( )的最短路問題.五年的最優(yōu)購置費(fèi)為 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )為頂點(diǎn)Xb1到Xrk6( )的最短路的權(quán).求 得 最 短 路 的 權(quán) 為 53， 而 兩 條 最 短 路 分 別 為 XXXXXXbrrbrr1213245162( )()( )();XX

20、XXXXbrbrrr1213415263( )( )()( )因 此 ， 計(jì) 劃 為 第 一 、 三 年 初 購 置 新 設(shè) 備 ， 或 第 一 、 四 年 初 購 置 新 設(shè) 備 ，五 年 費(fèi) 用 均 最 省 ， 為 53.34也可構(gòu)造加權(quán)有向圖 G2(V,E).（1）頂點(diǎn)集 V=V V V V V V123456,，Vi表第 i 年初購置新設(shè)備的決策，V6表第五年底.（2）弧集 E=(,)V Vij，i=1,2,3,4,5; ij6,弧(,)V Vij表第 i 年初購進(jìn)一臺(tái)設(shè)備一直使用到第 j 年初的決策，其權(quán) W(,)V Vij表由這一決策在第 i 年初到第 j 年初的總費(fèi)用，如W(,)

21、V V14=11+5+6+8=30.（3）問題轉(zhuǎn)化為求V1到V6的最短路問題，求得兩條最短路為VVV146，VVV136，權(quán)為 53，與圖 G1(V,E)的解相同返回返回35（2） 計(jì)算在各點(diǎn)iv設(shè)立服務(wù)設(shè)施的最大服務(wù)距離)(ivS max)(1ijjidvS , 2 , 1i 選址問題選址問題-中心問題中心問題例例 2某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示問應(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)3605 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8