最短路問(wèn)題DijkstraFloyd算法_第1頁(yè)
最短路問(wèn)題DijkstraFloyd算法_第2頁(yè)
最短路問(wèn)題DijkstraFloyd算法_第3頁(yè)
最短路問(wèn)題DijkstraFloyd算法_第4頁(yè)
最短路問(wèn)題DijkstraFloyd算法_第5頁(yè)
已閱讀5頁(yè),還剩43頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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ì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論