Dijkstra算法詳細(xì)講解.doc_第1頁(yè)
Dijkstra算法詳細(xì)講解.doc_第2頁(yè)
Dijkstra算法詳細(xì)講解.doc_第3頁(yè)
Dijkstra算法詳細(xì)講解.doc_第4頁(yè)
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、最短路徑之 Dijkstra算法詳細(xì)講解最短路徑算法在日常生活中,我們?nèi)绻枰3M?A 地區(qū)和 B地區(qū)之間,我們最希望知道的可能是從 A 地區(qū)到 B 地區(qū)間的眾多路徑中,那一條路徑的路途最短。最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題, 旨在尋找圖(由結(jié)點(diǎn)和路徑組成的)中兩結(jié)點(diǎn)之間的最短路徑。 算法具體的形式包括:()確定起點(diǎn)的最短路徑問題:即已知起始結(jié)點(diǎn),求最短路徑的問題。()確定終點(diǎn)的最短路徑問題:與確定起點(diǎn)的問題相反,該問題是已知終結(jié)結(jié)點(diǎn),求最短路徑的問題。在無(wú)向圖中該問題與確定起點(diǎn)的問題完全等同,在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。()確定起點(diǎn)終點(diǎn)的最短路徑問

2、題:即已知起點(diǎn)和終點(diǎn),求兩結(jié)點(diǎn)之間的最短路徑。()全局最短路徑問題:求圖中所有的最短路徑。用于解決最短路徑問題的算法被稱做 “最短路徑算法 ”, 有時(shí)被簡(jiǎn)稱作 “路徑算法 ”。 最常用的路徑算法有: Dijkstra 算法、 A*算法、 Bellman-Ford 算法、 Floyd-Warshall 算法、 Johnson 算法。本文主要研究 Dijkstra算法的單源算法。 Dijkstra 算法2.1Dijkstra算法Dijkstra 算法是典型最短路算法,用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展,直到擴(kuò)展到終點(diǎn)為止。 Dijkstra 算法能得出最

3、短路徑的最優(yōu)解,但由于它遍歷計(jì)算的節(jié)點(diǎn)很多,所以效率低。Dijkstra 算法是很有代表性的最短路算法,在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹,如數(shù)據(jù)結(jié)構(gòu),圖論,運(yùn)籌學(xué)等等。2.2Dijkstra算法思想Dijkstra算法思想為:設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖,把圖中頂點(diǎn)集合V分成兩組,第一組為已求出最短路徑的頂點(diǎn)集合(用 S 表示,初始時(shí) S 中只有一個(gè)源點(diǎn),以后每求得一條最短路徑,就將 加入到集合 S 中,直到全部頂點(diǎn)都加入到 S 中,算法就結(jié)束了),第二組為其余未確定最短路徑的頂點(diǎn)集合(用U表示),按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S 中。在加入的過程中,總保持從源點(diǎn)

4、 v 到 S 中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn) v 到 U 中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外,每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離, S 中的頂點(diǎn)的距離就是從 v 到此頂點(diǎn)的最短路徑長(zhǎng)度, U 中的頂點(diǎn)的距離,是從 v 到此頂點(diǎn)只包括 S 中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。2.3Dijkstra算法具體步驟。(1)初始時(shí), S 只包含源點(diǎn),即 S, v 的距離為 0。U 包含除 v 外的其他頂點(diǎn), U 中頂點(diǎn) u 距離為邊上的權(quán)(若 v 與 u 有邊)或 )(若 u 不是 v 的出邊鄰接點(diǎn))。(2)從 U 中選取一個(gè)距離 v 最小的頂點(diǎn) k,把 k,加入 S 中(該選定的距離就是 v 到 k 的最短路徑長(zhǎng)

5、度)。(3)以 k 為新考慮的中間點(diǎn),修改 U 中各頂點(diǎn)的距離;若從源點(diǎn) v 到頂點(diǎn)u(u U)的距離(經(jīng)過頂點(diǎn) k)比原來(lái)距離(不經(jīng)過頂點(diǎn) k)短,則修改頂點(diǎn) u 的距離值,修改后的距離值的頂點(diǎn) k 的距離加上邊上的權(quán)。(4)重復(fù)步驟( 2)和( 3)直到所有頂點(diǎn)都包含在S 中。2.4Dijkstra算法舉例說(shuō)明如下圖,設(shè) A 為源點(diǎn),求 A 到其他各頂點(diǎn)( B、C、D、E、 F)的最短路徑。線上所標(biāo)注為相鄰線段之間的距離,即權(quán)值。 (注:此圖為隨意所畫,其相鄰頂點(diǎn)間的距離與圖中的目視長(zhǎng)度不能一一對(duì)等)圖一: Dijkstra無(wú)向圖算法執(zhí)行步驟如下表:【注:圖片要是看不到請(qǐng)到“相冊(cè) - 日志

6、相冊(cè) ”中,名為 “Dijkstra算法過程 ”的圖就是了】錯(cuò)誤 !步驟S 集合中U 集合中1選入 A,此時(shí) S=U=此時(shí)最短路徑 AA=0A B=6,A C=3,以 A 為中間點(diǎn),從 A 開始找A 其它 U中的頂點(diǎn) =,發(fā)現(xiàn) A C=3權(quán)值為最短2選入 C,此時(shí) S=U=此時(shí)最短路徑 AA=0,A C=3以 C 為中間。- 4 -。點(diǎn),A C B=5(比上面第一步的 A B=6要短 )從 A C=3這條最短路徑開始找此時(shí)到 D權(quán)值更改為 A C B=5,A C D=6,A C E=7,A C 其它 U 中的頂點(diǎn) =,發(fā)現(xiàn) A C B=5權(quán)值為最短3選入 B,此時(shí) S=U=此時(shí)最短路徑 AA=

7、0,A C=3,A C B=5A C BD=10( 比上面第二步的以 B 為中間點(diǎn)A C D=6要長(zhǎng) )從 A CB=5這條最短路徑開始找此時(shí)到 D權(quán)值更改為 A C D=6,A C B其它 U 中的頂點(diǎn) =,發(fā)現(xiàn)A C D=6權(quán)值為最短4選入 D,此時(shí) S=U=此時(shí)最短路徑 AA=0, AC=3,A C DE=8( 比上面第二步的 A C E=7A C B=5, A CD=6要長(zhǎng) ) 此時(shí)到 E 權(quán)值更改為 A C E=7,以 D 為中間點(diǎn),A C DF=9從 A CD=6這條最短路徑開始找發(fā)現(xiàn) A C E=7權(quán)值為最短5選入 E,此時(shí) S=U=此時(shí)最短路徑 AA=0, AC=3,A C EF=12( 比上面第四步的A C B=5,AC D=6,A C E=7,以 EA C DF=9要長(zhǎng) ) 此時(shí)到 F 權(quán)值更改為為中間點(diǎn),A C DF=9從 A CE=7這條最短路徑開始找發(fā)現(xiàn) A C D F=9權(quán)值為最短6選入 F,此時(shí) S=U 集合已空,查找完畢

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論