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

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

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

3、的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。算法描述(這里描述的是從節(jié)點(diǎn)1開(kāi)始到各點(diǎn)的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 +無(wú)窮大(1.i之間不存在邊)2 在S中，令d(j)=mind(i),i屬于S，令S=S-j，若S為空集則算法結(jié)束，否則轉(zhuǎn)33 對(duì)全部i屬于S,如果存在邊j->i，那么置d(i)=mind(i), d(j)+Wj->i，轉(zhuǎn)2Dijkstra算法思想為：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)

4、集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中，總保持從源點(diǎn)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)度。算法具體步驟（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)度）。（3）以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u（u U）的距離（經(jīng)過(guò)頂點(diǎn)k）比原來(lái)距離（不經(jīng)過(guò)頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。（4）重復(fù)步驟（2）和（3）直到所有頂點(diǎn)都包