最短路徑算法—Dijkstra 總結(jié)

1、Dijkstra 算法解釋本文引用三篇文章：分別是 謝光新-Dijkstra 算法，zx770424 -Dijkstra 算法，中華兒女英雄 -Dijkstra 算法有興趣的朋友請引用原文，由于分類很不相同難以查找，此處僅作匯總。謝光新 的文章淺顯易懂，無需深入的數(shù)學(xué)功力，每一步都有圖示，很適合初學(xué)者了解。zx770424 將每一步過程，都用圖示方式和公式代碼偽代碼對應(yīng)也有助于，代碼的理解。中華兒女英雄 從大面上總結(jié)了Dijkstra 的思想，并將演路圖描敘出來了。起到總結(jié)的效果。希望這篇匯總有助于大家對Dijkstra 算法的理解。Dijkstra算法是典型最短路算法，用

2、于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。簡介Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運籌學(xué)等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標(biāo)號方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時標(biāo)號

3、的方式。注意該算法要求圖中不存在負權(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)=mind(i),i屬于S，令S=S-j，若S為空集則算法結(jié)束，否則轉(zhuǎn)33 對全部i屬于S,如果存在邊j->i，那么置d(i)=mind(i), d(j)+Wj->i，轉(zhuǎn)2Dijkstra算法思想為：設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點

4、集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。算法具體步驟（1）初始時，S只包含源點，即S=，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權(quán)（若v與u有邊）或 ）（若u不是v的出邊鄰接點）。（2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u U）的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。（4）重復(fù)步驟（2）和（3）直到所有頂點都包