資源描述：
《最短路徑算法—Dijkstra 總結(jié).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、Dijkstra算法解釋本文引用三篇文章：分別是謝光新-Dijkstra算法，zx770424?-Dijkstra算法，中華兒女英雄?-Dijkstra算法有興趣的朋友請引用原文，由于分類很不相同難以查找，此處僅作匯總。謝光新的文章淺顯易懂，無需深入的數(shù)學(xué)功力，每一步都有圖示，很適合初學(xué)者了解。zx770424將每一步過程，都用圖示方式和公式代碼偽代碼對應(yīng)也有助于，代碼的理解。中華兒女英雄從大面上總結(jié)了Dijkstra的思想，并將演路圖描敘出來了。起到總結(jié)的效果。希望這篇匯總有助于大家對Dijk
2、stra算法的理解。12Dijkstra算法是典型最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。簡介 Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介
3、紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運籌學(xué)等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標(biāo)號方式，一種是用OPEN,CLOSE表的方式，這里均采用永久和臨時標(biāo)號的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。算法描述 (這里描述的是從節(jié)點1開始到各點的dijkstra算法，其中Wa->b表示a->b的邊的權(quán)值，d(i)即為最短路徑值) 1．置集合S={2,3,...n},?數(shù)組d(1)=0,d(i)=W1->i(1,i之間存在邊)or+無窮大(1.i之間不存在邊) 2．在S中，令d(j)=min
4、{d(i),i屬于S}，令S=S-{j}，若S為空集則算法結(jié)束，否則轉(zhuǎn)3 3．對全部i屬于S,如果存在邊j->i，那么置d(i)=min{d(i),d(j)+Wj->i}，轉(zhuǎn)2 Dijkstra算法思想為：設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑,就將加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次
5、把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度?！ ∷惴ň唧w步驟 ?。?）初始時，S只包含源點，即S=，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權(quán)（若v與u有邊）或）（若u不是v的出邊鄰接點）。 ?。?）從U中選取一個距離v最小的頂點k，把k，加入S
6、中（該選定的距離就是v到k的最短路徑長度）?！ 。?）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（uU）的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。 ?。?）重復(fù)步驟（2）和（3）直到所有頂點都包含在S中。復(fù)雜度分析 Dijkstra算法的時間復(fù)雜度為O(n^2)12空間復(fù)雜度取決于存儲方式，鄰接矩陣為O(n^2)1212121212121212Dijkstra算法的基本思想是：1212
