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

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

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

3、方式。注意該算法要求圖中不存在負(fù)權(quán)邊。算法描述(這里描述的是從節(jié)點1開始到各點的 dijkstra算法，其中 Wa->b表示a->b的邊的權(quán)值，d即為最短路徑值)1. 置集合S=2,3，n,數(shù)組d(1)=0, d(i尸W1->i(1,i之間存在邊)or +無窮大之間不存在邊)2. 在S中，令d(j)=mind,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)有向圖，把圖中頂點集合V分成兩組，第一組為已求出

4、最短路徑的頂點集合(用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中頂點

5、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)直到所有頂點都包含在S中。復(fù)雜度分析Dijkstra算法的時間復(fù)雜度為0mA2)空間復(fù)雜度取決于存儲方式，鄰接矩陣為0(nA2)迪杰斯特拉（Dijkstra）算法是單源頂點最短路徑求解算法。木例以VI結(jié)點（1”結(jié)點

6、）為計算源。有向圖與鄰接矩陣:有向網(wǎng)絡(luò)鄰接矩陣121 r oio2 8o3 O0004 88345g 3010050 B 80«1020060880算法的動態(tài)執(zhí)行情況表格中的項目說明:1、循環(huán)：執(zhí)行算法的次數(shù)。2、源：通過運算后，當(dāng)前已被加入的結(jié)點©3、K+1：本次運兌新加入的結(jié)點。4、目的結(jié)點開銷：從源結(jié)點到目的結(jié)點最優(yōu)路件的開銷45、前卵結(jié)點：所力.結(jié)點按照最優(yōu)路徑，逆回到VI結(jié)點的上一個結(jié)點。運算過程：步驟1:步驟2：步驟3：步驟4：步驟5：循環(huán)源-1目的結(jié)點開銷前項結(jié)點1234512345初始化1010max30100010111(1,220106030100012

7、112“2用40105030100014113(L2.43130105030600141341.243.5)501050306001413持加入節(jié)點：75 加入V5當(dāng)前到V5的彷路TF：VI今V5,開俏:100V1)V4)V5, JTfil： 90VI -»V4->V3->V5.開箱：60 優(yōu)堆開梢為60的鏈路.最短路的算法一Dijkstra莫.法在圖G中，給定s和I兩個頂點。從s到I可以有多條路徑,從這多條路中找出長度最 小的路，這樣的路稱為從s到t的最短跖。設(shè)每條弧的長度均為非負(fù)值。下面的第法是由狄克斯特拉(Dijkslra, 1959)提出的，其想法是：設(shè)已知圖中最

8、接近 頂點s的m個頂點以及從頂點s到這些頂點中每一個頂點的最短路(從s到其本身的最短 路是零路，即沒有.弧的路，KK度為0).對頂點s和這m個頂點著色。然后，最接近于s ©的笫mH個頂點可如卜求之：對于每一個未著色的頂點y,考慮所TT已著色頂點x,把弧(x, y)接在從s到x的最 短路后面，這樣就得到從"到y(tǒng)的m條不同路。從這皿條路中選出最短的路，它就是從s 到y(tǒng)的最短路。相應(yīng)的y點就是最接近于s的第mH個頂點。因為所有孤的長度都是非負(fù)值, 所以從。到最接近于s的笫m+1個頂點的最短路必然只使用己著色的頂點作為中間頂點。從nr()升始，符這個過程重復(fù)進行卜去，直至求得從s到

9、t的最短路為止。算法；狄克斯特拉班短路匏法第1步開始，所有弧和頂點都未著色0對每個頂點x指定一個數(shù)d(x), d(x)表示從s到x 的最短路的K度(中間頂點均已著色開始時，令d(s)-0, d(x)=g (對所仃xKs)。y表 示己著色的最后一個頂點。對始點s著色,令yr。第2步對于每個未著色頂Hx,重新定義d(x)如下：d(x)=min( d(x). d (y)+a(y, x)公式對于所有犬著色頂點x，如d(x)=8,則算法定止。因為此時從s到任一未著色的頂點都沒 有路。否則，對具有d(x)最小值的未著色頂點k進行著色。同時把弧(y, x)著色(指向頂 點x的弧只有一條被著色)。令y=xo第

10、3步如果頂點t已著色，則算法終上。這時已找到一條從s到t的最短路。如果t未看 色，則轉(zhuǎn)第2步。注意；已著色的弧不能構(gòu)成一個圈，而是構(gòu)成一個根在s的樹形圖，此樹形圖稱為最短路樹 形圖。若X姑最短路樹形圖中的任一頂點，則從S到X的唯一的一條路是從S到X的最短路. 這個算法可以看成是根在頂點S的樹形圖的生K過程。一月到達(dá)頂點t,生K過程就停止。 例：給定不向圖如下圖所示，用狄克斯特拉算法找出從S到I的最短路徑。第1步d(a)=min d(a), d(s)+a(s, a) 1=min (o°, 0+4) =4d(b)-ir)in d (b), d(s)+a(s, b)=min00, 0+7=

11、7d(r) =min ( d(c), d (s)+a(s, c)=min(8, 0+3) =3d(d) =min d(d), d(s) +a(s, d)=min 00, 0+8)=8d(t)=min d(t), d(s)+a(s, t)=min (oo, 0»co)=o0由丁 d(c)=3是最小值，所以對c點著色,并對確定d(c)的弧(s,c)著色。見圖a)。第3步頂點I未著色，返回第2步，1a)第2步y(tǒng)=dd(a)=minl d(a), d(c)+a(c,a)二 min 4.3+8)二 4d(b)=nin d(b), d(c)+a(c,b)Fin (7. 3+8二7d(d)nin(

12、 d(d)9 d(c) *a(c, d)二min 8, 3+3 =6d(t)=min d(t), d(c)+a(c, t)=min(8,3+8 =co由于d(a)=4是最小優(yōu)，所以對頂點a著色.并對確定d(a)的孤著色.見圖h).第3步 頂點工未著色，返回第2步.第2步y(tǒng)=ad(b)=min ( d(b), d (a)1 a (a, b)=min (7, 4+3 =7d(d) =min ( d(d), d (a) +a (at d) =min (6t 4+2 =6d(t)=nin( d(t)» d(a) +a(at t) =min g 4- eo)=©od(d)=6是最小位

13、，對d著色，確定d(d)的弧有兩條(即(c,d)和(a, d),可任選其中的條,對其著色,我們選(c,d)見圖c)第3加頂點1未看色,返I可第2米.d(b) =min cl (b), d(d)+a(d, b)=min 7, 6+°°=7d(t)=min d(t), d(d)+a(d, l)i n 00, 6+2 =8d(b)=7是最小值,對點b著色,對確定d(b)的弧(s,b)著色。見圖d)。第3步頂點t未著色，返回第2步。第2步y(tǒng)=bd(t)=min d(t), d (b) +a (b, t)=niin(8, 7+2|=8對點i及弧(d, 1)著色最終的最短路樹形圖由弧(

14、s, c) (s, a) (c, d)(s, h)利(d, t) 組成，見圖e)。從s到t的最短路由弧(s, c) (c, d)和(d, t)組成，其長度為3+3+2=8。e)Dijkstra算法的基本思想是:設(shè)目的節(jié)點（就恂造spf例而言，是相節(jié)點）為h 任一條福跳"，）的長度為為， 怖個小點，到我的最也跣徑長度估計為。小 定義所仃節(jié)點的集合為a,定義集合戶曰4, 并設(shè)定集ft P晌初始值為P = 外0在算法迭代的過程中，如果。&已經(jīng)變成一個確定值，則將j標(biāo)尼為固定點，并將其加 入比合尸*在外法的每一步迭代中，在尸以外的H點中，必定是選擇與目的節(jié)點我最近的 ”點加入到尸中.

15、算法的R陣步驟如下:”<.）尸=£ %=。， jwP. f若J和&不是相鄰節(jié)點，則=a求解使4 = min D.成。的八，w . 即尋找下一個和目的節(jié)點最近的節(jié)點：令P=PUi-/2二八，算法第束口（3）對所用/匚7.置0井=呷n/）9 R+dJ,返I可4獴2）這樣.通過一心上的迭代，就M以求出某一外點到算他每一個節(jié)點的最旬路存，也就是 說.構(gòu)造出了以該節(jié)點為根節(jié)點的$PF樹.卜面是利用Dijkstra即法構(gòu)冷SPF期的一個例子。圖23示一個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).箸個路由器以及各條情廊的代價已經(jīng)標(biāo)出.現(xiàn)在計科 以R為根節(jié)點的5PF樹，來說明Dijk5g算法的I作過程：82 J3DijkMra算法成川舉例求解以RI為根力點的SP卜樹的兒驟如下:（1） P = m,很顯然，與R1直接相鄰的節(jié)點只有R2和R3,其中Dr” =八=6 , 。沏="科九=I，其他節(jié)點到R1的蹈禹都是無窮大（因為沒書和R1鄰接）.（2）在4加和W中，Dr31a蚊小,所以下一個即離R1最近的節(jié)點i是R3,曲昌為 I：此