第8講 最短路問題ppt課件

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

2、示示1、 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣2、 鄰接矩陣鄰接矩陣返回返回4定義定義有序三元組G=(V,E, )稱為一個圖圖.1 V=,21nvvv是有窮非空集，稱為頂點集頂點集， 其中的元素叫圖 G 的頂點頂點.2 E 稱為邊集邊集，其中的元素叫圖 G 的邊邊.3 是從邊集 E 到頂點集 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 中頂點的無序偶 vivj相對應(yīng)的邊 e，稱為圖的無無向向邊邊.每一條邊都是無向邊的圖，叫無無向向圖圖；每一條邊都是有向邊的圖，稱為有有向向圖圖；既有無向邊又有有向邊的圖稱為混混合合圖圖.定義定義若將圖 G 的每一條邊 e 都對應(yīng)一個實數(shù) w(e)，稱 w(e)為邊的權(quán)權(quán)，并稱圖 G 為賦賦權(quán)權(quán)圖圖.規(guī)定用記號和分別表示圖的頂點數(shù)和邊數(shù).6常用術(shù)語：（） 端點相同的邊稱為環(huán)環(huán)（） 若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊重邊（） 有邊聯(lián)結(jié)的兩個頂點稱為相鄰的頂點相鄰的頂點，有一個公共端點的

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

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

6、的圖 G 的邊為邊集的圖 G 的子圖，稱為 G 的由由 V1導(dǎo)導(dǎo)出出的的子子圖圖，記為 GV1.(3)設(shè) E1E,且 E1,以 E1為邊集,E1的端點集為頂點集的圖 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)與若的終點是若的起點是若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、、固 定定 起起 點點 的的 最最 短短 路路三、每三、每 對對 頂頂 點點 之之 間間 的的 最最 短短 路路返回返回15基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路徑4521141vevevPvv定定義義在無向圖 G=(V,E,)中：（） 頂點與邊相互交錯且iiivve1)( (i=1,2,k)的有限非空序列)(12110kkkvevevevw稱為一條從0v到kv的通通路路，記為kvvW0（）邊不重復(fù)但頂點可重復(fù)的通路稱為道道路路，記為kvvT0（）邊與頂點均不重復(fù)的通路稱為路路徑徑，記為kvvP016

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

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

12、法2、求路徑矩陣的方法、求路徑矩陣的方法3、查找最短路路徑的方法、查找最短路路徑的方法（一）算法的基本思想（一）算法的基本思想（三）算法步驟（三）算法步驟返回返回24算法的基本思想算法的基本思想 直接在圖的帶權(quán)鄰接矩陣中用插入頂點的方法依次構(gòu)造出個矩陣 D(1)、 D(2)、 、D()，使最后得到的矩陣 D()成為圖的距離矩陣，同時也求出插入點矩陣以便得到兩點間的最短路徑返回返回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作為中間點的路徑中最短路的長度（2）D(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是從 vi到 vj的只允許以 v1 、 v2作為中間點的路徑中最短路的長度（）D()=)()(ijd，其中)1()1()(,miniijijddd) 1( jd)(ijd是從 vi到 vj的只允許以 v1、v2、v作為中間點的路徑中最短路的長度即是從 vi到 vj中間可插入任何頂點的路徑中最短路的長，因此D()即是距離矩陣返回返回26算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法R=

14、)(ijr, rij的含義是從 vi到 vj的最短路要經(jīng)過點號為 rij的點)()0()0(ijrR, jrij)0(每求得一個 D(k)時，按下列方式產(chǎn)生相應(yīng)的新的 R(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距離矩陣的同時可建立路徑矩陣R 即當(dāng)vk被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求 時求得 ，可由 來查找任何點對之間最短路的路徑)(D)(R)(R返回返回27ij算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點 p1是點 i 到點 j 的最短路的中間點.然后用同樣的方法再分頭查找若：（） 向點

15、 i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向點 j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm則由點i到j(luò)的最短路的路徑為：jqqqpppimk,21, 12返回返回28算法步驟算法步驟Floyd算算法法：求任意兩點間的最短路D(i,j)：i 到 j 的距離R(i,j)：i 到 j 之間的插入點輸入: 帶權(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)圖的任意兩點間的距離與路徑 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è)使用一臺設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設(shè)備，就要支付一定的購置費用；若繼續(xù)使用，則需支付一定的維修費用.現(xiàn)要制定一個五年之內(nèi)的設(shè)備更新計劃，使得五年內(nèi)總的支付費用最少. 已知該種設(shè)備在每年年初的價格為：第一年第二年第三年第四年第五年1111121213 使用不同時間設(shè)備所需維修費為：使用年限0112233445維修費568111832構(gòu)造加權(quán)有向圖 G1(V,E)（1）頂點集 VXib , i=1,2,

18、3,4,5Xirk( ), i=2,3,4,5,6; k=1,2,i-1,每個頂點代表年初的一種決策，其中頂點Xib代表第 i 年初購置新設(shè)備的決策，頂點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，則頂點Xi與Xi1之間有弧(Xi,Xi1)，其權(quán) W(Xi,Xi1)代表

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

20、XXXXbrbrrr1213415263( )( )()( )因 此 ， 計 劃 為 第 一 、 三 年 初 購 置 新 設(shè) 備 ， 或 第 一 、 四 年 初 購 置 新 設(shè) 備 ，五 年 費 用 均 最 省 ， 為 53.34也可構(gòu)造加權(quán)有向圖 G2(V,E).（1）頂點集 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 年初購進一臺設(shè)備一直使用到第 j 年初的決策，其權(quán) W(,)V Vij表由這一決策在第 i 年初到第 j 年初的總費用，如W(,)

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