




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
最短路問(wèn)題
趙嘉誠(chéng)Dijkstra算法Ford算法Floyd算法SPFA算法一、什么是最短路問(wèn)題例下圖為單行線(xiàn)交通網(wǎng),每弧旁的數(shù)字表示通過(guò)這條線(xiàn)所需的費(fèi)用?,F(xiàn)在某人要從v1出發(fā),通過(guò)這個(gè)交通網(wǎng)到v8去,求使總費(fèi)用最小的旅行路線(xiàn)。v2v523464v3v1v4v6121061210v8v9v72363從v1到v8:P1=(v1,v2,v5,v8)費(fèi)用6+1+6=13P2=(v1,v3,v4,
v6,
v7,v8)費(fèi)用3+2+10+2+4=21P3=……旅行路線(xiàn)總費(fèi)用路上所有弧權(quán)之和。最短路問(wèn)題中,不考慮有向環(huán)、并行弧。即適用于DAG(有向無(wú)環(huán)圖)v2v523464v3v1v4v6121061210v8v9v72363最短路問(wèn)題嚴(yán)格的定義
給定有向網(wǎng)絡(luò)D=(V(點(diǎn)),A(?。?,W(權(quán))),任意弧aij∈A,有權(quán)w(
aij
)=wij,給定D中的兩個(gè)頂點(diǎn)A,B。設(shè)P是D中從A到B的一條路,定義路P的權(quán)(長(zhǎng)度)是P中所有弧的權(quán)之和,記為w(P)。最短路問(wèn)題就是要在所有從vs到vt的路中,求一條路P0,使
稱(chēng)P0是從vs到vt的最短路。路P0的權(quán)稱(chēng)為從vs到vt的路長(zhǎng)。記為ust。最短路徑問(wèn)題是圖論研究中的一個(gè)經(jīng)典算法問(wèn)題,旨在尋找圖(由結(jié)點(diǎn)和路徑組成的)中兩結(jié)點(diǎn)之間的最短路徑。算法具體的形式包括:確定起點(diǎn)的最短路徑問(wèn)題-即已知起始結(jié)點(diǎn),求最短路徑的問(wèn)題。確定終點(diǎn)的最短路徑問(wèn)題-與確定起點(diǎn)的問(wèn)題相反,該問(wèn)題是已知終結(jié)結(jié)點(diǎn),求最短路徑的問(wèn)題。在無(wú)向圖中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同,在有向圖中該問(wèn)題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問(wèn)題。確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題-即已知起點(diǎn)和終點(diǎn),求兩結(jié)點(diǎn)之間的最短路徑。全局最短路徑問(wèn)題-求圖中所有的最短路徑。二、Dijkstra(迪杰特斯拉)算法
當(dāng)所有
wij
≥0時(shí),本算法是用來(lái)求給定點(diǎn)vs到任一個(gè)點(diǎn)vj最短路的公認(rèn)的最好方法。事實(shí):如果P是D中從vs到vj的最短路,vi是P中的一個(gè)點(diǎn),那么,從vs沿P到vi的路是從vs到vi的最短路。
最短路的子路也是最短路。Dijkstra算法是典型的最短路徑路由算法,用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展,直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解,但由于它遍歷計(jì)算的節(jié)點(diǎn)很多,所以效率低。
思想:將D=(V,A,W)中vs到所有其它頂點(diǎn)的最短路按其路長(zhǎng)從小到大排列為:u0≤u1≤u2≤…≤unu0表示vs到自身的長(zhǎng)度,相應(yīng)最短路記為:P0,P1,P2,…,Pn,取最小值的點(diǎn)為v1,∴P1=P(vs,v1)
假定u0,u1,…,uk的值已求出,對(duì)應(yīng)的最短路分別為P1=P(vs,v1),P2=P(vs,v2),…,Pk=P(vs,vk)P1一定只有一條弧。
記則
使上式達(dá)到最小值的點(diǎn)v’可取為vk+1。
計(jì)算過(guò)程中可采用標(biāo)號(hào)方法。Xk中的點(diǎn),ui值是vs到vi的最短路長(zhǎng)度,相應(yīng)的點(diǎn)記“永久”標(biāo)號(hào);
XK中的點(diǎn),ui值是vs到vi的最短路長(zhǎng)度的上界,相應(yīng)的點(diǎn)記“臨時(shí)”標(biāo)號(hào),供進(jìn)一步計(jì)算使用。前點(diǎn)標(biāo)號(hào)
i:表示點(diǎn)vs到vj的最短路上vj的前一點(diǎn)。如
i=m,表示vs到vj的最短路上vj前一點(diǎn)是vm。6圖上標(biāo)號(hào)法:v5v223464v3v1v41210
61210v8v9v72363v60∞∞1∞∞∞36圖上標(biāo)號(hào)法:v5v223464v3v1v41210
61210v8v9v72363v60∞∞1∞∞∞36v5v223464v3v1v41210
61210v8v9v72363v60∞111∞∞∞3圖上標(biāo)號(hào)法:1,5v5v223464v3v1v41210
61210v8v9v72363v60∞111∞∞∞36圖上標(biāo)號(hào)法:1,5v5v223464v3v1v41210
61210v8v9v72363v60∞111∞∞∞35圖上標(biāo)號(hào)法:5v5v223464v3v1v41210
61210v8v9v72363v60∞111∞∞3∞圖上標(biāo)號(hào)法:5v5v223464v3v1v41210
61210v8v9v72363v60∞111∞∞36圖上標(biāo)號(hào)法:5v5v223464v3v1v41210
61210v8v9v72363v60111∞6∞3∞圖上標(biāo)號(hào)法:5v5v223464v3v1v41210
61210v8v9v72363v60101∞61239圖上標(biāo)號(hào)法:5v5v223464v3v1v41210
61210v8v9v72363v60101∞61239圖上標(biāo)號(hào)法:Dijkstra算法步驟:第1步:令us=0,uj=wsj
(1≤j≤n)若asjA,則第2步:(選永久標(biāo)號(hào))在XK中選一點(diǎn)vi,滿(mǎn)足第3步:(給點(diǎn)vi永久性標(biāo)號(hào))第4步:(修改臨時(shí)標(biāo)號(hào))對(duì)所有如果
令
j=i,uj=ui+wij否則,
i,,uj
不變,把k換成k+1,返回第2步。如果ui=+
,停止,令Xk+1=Xk∪﹛vi﹜,Xk+1=Xk\﹛vi﹜令wsj=+,X0={vs},X0=V\X0,k=0,
i=0(0≤j≤n)從vs到XK中各點(diǎn)沒(méi)有路;否則,轉(zhuǎn)第3步。如果Xk+1=
,結(jié)束,到所有的點(diǎn)的最短路已經(jīng)求得;否則,轉(zhuǎn)第4步。例用Dijkstra算法求前面例子中從v1到各點(diǎn)的最短路。解:u1=0,u2=6,u3=3,u4=1,u5=u6=u7=u8=u9=+
,
j=1(j=2,3,…,9)X0={v1},X0={v2,v3,…,v9}v2v523464v3v1v4v6121061210v8v9v72363K=0∵min{u2,u3,u4,u5,u6,u7,u8,u9}=min{6,3,1,,,,,}=1=u4
∴點(diǎn)v4得永久標(biāo)號(hào),
4=1,X1={v1,v4},
X1={v2,v3,
v5,v6
,v7,v8,v9},在所有vj∈X1中,∵u6=
,u4+w46=1+10=11,即u4+w46<u6
∴修改臨時(shí)標(biāo)號(hào)u6=11
,
6=4,其余標(biāo)號(hào)不變。v2v523464v3v1v4v6121061210v8v9v72363K=0+1=1∵min{u2,u3,u5,u6,u7,u8,u9}=min{6,3,,11,,,}=3=u3
∴點(diǎn)v3得永久標(biāo)號(hào),
3=1,X2={v1,v4,v3},
X2={v2,
v5,v6
,v7,v8,v9},
∵u2=6
,u3+w32=3+2=5,即u3+w32<u2∴修改臨時(shí)標(biāo)號(hào)u2=5
,
2=3,其余標(biāo)號(hào)不變。在所有vj∈X2中,k=2+1=3∵min{u5,u6,u7,u8,u9}=min{6,11,,,}=6=u5
∴點(diǎn)v5得永久標(biāo)號(hào),
5=2,
X4={v1,v4,v3,v2,
v5},X4={v6
,v7,v8,v9},
∵u6=11
,u5+w56=6+4=10,即u5+w56<u6
u7=
,u5+w57=6+3=9,即u5+w57<u7
u8=
,u5+w58=6+6=12,即u5+w58<u8∴修改臨時(shí)標(biāo)號(hào)u6=10
,
6=5,u7=9,
7=5,
u8=12
,
8=5,在所有vj∈X4中,K=3+1=4∵min{u6,u7,u8,u9}=min{10,9,12,
}=9=u7
∴點(diǎn)v7得永久標(biāo)號(hào),
7=5,X2={v1,v4,v3,
v2,
v5,v7},X2={v6
,v8,v9},在vj∈X5中,臨時(shí)標(biāo)號(hào)不變。K=4+1=5∵min{u6,u8,u9}=min{10,12,
}=10=u6
∴點(diǎn)v6得永久標(biāo)號(hào),
6=5,X6={v1,v4,v3,
v2,
v5,v7
,v6},X6={v8,v9},點(diǎn)v8,v9臨時(shí)標(biāo)號(hào)不變。K=5+1=6∵min{u8,u9}=min{12,
}=12=u8
∴點(diǎn)v8得永久標(biāo)號(hào),
8=5,即從v1到v8的最短路長(zhǎng)為u8=12,
∵
8=5,
5=2,
2=3,
3=1,
知從v1到v8的最短路為:
P1,8=P(v1,v3,
v2,
v5,v8)v2v523464v3v1v4v6121061210v8v9v72363問(wèn)題:①本例中,v1到v9的最短路?②無(wú)向網(wǎng)絡(luò):③負(fù)權(quán)弧時(shí)。wijvivjwijwijvjvi無(wú)向網(wǎng)絡(luò)中,最短路→最短鏈。④多個(gè)點(diǎn)對(duì)之間最短路?v1v2v312-3Dijkstra算法失效voidinit(){inti,j;for(i=1;i<=n;i++)//i==j的時(shí)候也可以初始化為0,只是有時(shí)候不合適for(j=1;j<=n;j++)mapp[i][j]=inf;}voiddijk(intu){inti,j,mins,v;for(i=1;i<=n;i++){dist[i]=mapp[u][i];mark[i]=false;}mark[u]=true;dist[u]=0;
while(1){mins=inf;for(j=1;j<=n;j++)if(!mark[j]&&dist[j]<mins)mins=dist[j],v=j;if(mins==inf)break;mark[v]=true;for(j=1;j<=n;j++)if(!mark[j]&&dist[v]+mapp[v][j]<dist[j])dist[j]=dist[v]+mapp[v][j];
}}三、Floyd算法
網(wǎng)絡(luò)G=(V,A,W),令D=(dij)n
n,表示G中vi到vj的最短路的長(zhǎng)度。
考慮G中任意兩點(diǎn)vi,vj,如將G中vi,vj以外的點(diǎn)都刪掉,得只剩vi,vj的一個(gè)子網(wǎng)絡(luò)G0,記wij為?。╲i,vj)的權(quán)。
在G0中加入v1及G中與vi,vj,v1相關(guān)聯(lián)的弧,得G1,G1中vi到vj的最短路長(zhǎng)記為,則一定有vivjv1wij
再在D1中加入v2及D中與vi,vj,v1,
v2相關(guān)聯(lián)的弧,得D2,D2中vi到vj的最短路長(zhǎng)記為,則有
遞推,D中n個(gè)點(diǎn)逐個(gè)加入子網(wǎng)絡(luò),終得D中vi到vj的最短路路長(zhǎng)
如果計(jì)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度保稅區(qū)預(yù)制塊生產(chǎn)配送、安裝與施工監(jiān)督合同
- 二零二五年度北京新能源汽車(chē)研發(fā)科研助理聘用協(xié)議
- 環(huán)球航行旅客合同細(xì)則
- 2025年合結(jié)鋼項(xiàng)目合作計(jì)劃書(shū)
- 2025年表面改性材料項(xiàng)目建議書(shū)
- 2025年水力發(fā)電機(jī)組合作協(xié)議書(shū)
- 2025湖北省建筑安全員-B證(項(xiàng)目經(jīng)理)考試題庫(kù)
- 2025貴州省建筑安全員《C證》考試題庫(kù)
- 2025河北省建筑安全員A證考試題庫(kù)
- 公寓樓裝修合同
- 非公開(kāi)發(fā)行公司債券的法律意見(jiàn)書(shū)模版
- 汽車(chē)空調(diào)技術(shù)與維修教案
- 企業(yè)管理概論-課件全書(shū)課件完整版ppt全套教學(xué)教程最全電子教案電子講義(最新)
- 圍手術(shù)期肺部感染
- 餐飲服務(wù)食品安全監(jiān)督量化分級(jí)動(dòng)態(tài)等級(jí)評(píng)定檢查表
- 北師大版語(yǔ)文選修《蕭蕭》ppt課件1
- 大學(xué)生職業(yè)素養(yǎng)課件-5第五單元學(xué)會(huì)有效溝通-PPT課件
- 《談骨氣》課文閱讀(共2頁(yè))
- 病原生物與免疫學(xué)(中職)緒論P(yáng)PT課件
- 新起點(diǎn)小學(xué)英語(yǔ)一年級(jí)上冊(cè)單詞卡片(共23頁(yè))
- 蝴蝶蘭PPT課件
評(píng)論
0/150
提交評(píng)論