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

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

2、一個(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算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。Dijkstra 一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN,CLOSES的方式，這里均采用永久和臨時(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即為最短路徑值)1. 置集合S=2,3，n,數(shù)組d(1)=0, d(i尸W1->i(1,i之間存在邊)or +無(wú)窮大之間不存在邊)2. 在S中，令d(j)=mind,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)集合V分成兩組，第一組為已求出

4、最短路徑的頂點(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)

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

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

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

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

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

10、3步如果頂點(diǎn)t已著色，則算法終上。這時(shí)已找到一條從s到t的最短路。如果t未看 色，則轉(zhuǎn)第2步。注意；已著色的弧不能構(gòu)成一個(gè)圈，而是構(gòu)成一個(gè)根在s的樹(shù)形圖，此樹(shù)形圖稱為最短路樹(shù) 形圖。若X姑最短路樹(shù)形圖中的任一頂點(diǎn)，則從S到X的唯一的一條路是從S到X的最短路. 這個(gè)算法可以看成是根在頂點(diǎn)S的樹(shù)形圖的生K過(guò)程。一月到達(dá)頂點(diǎn)t,生K過(guò)程就停止。 例：給定不向圖如下圖所示，用狄克斯特拉算法找出從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是最小值，所以對(duì)c點(diǎn)著色,并對(duì)確定d(c)的弧(s,c)著色。見(jiàn)圖a)。第3步頂點(diǎn)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)，所以對(duì)頂點(diǎn)a著色.并對(duì)確定d(a)的孤著色.見(jiàn)圖h).第3步 頂點(diǎn)工未著色，返回第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、，對(duì)d著色，確定d(d)的弧有兩條(即(c,d)和(a, d),可任選其中的條,對(duì)其著色,我們選(c,d)見(jiàn)圖c)第3加頂點(diǎn)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是最小值,對(duì)點(diǎn)b著色,對(duì)確定d(b)的弧(s,b)著色。見(jiàn)圖d)。第3步頂點(diǎn)t未著色，返回第2步。第2步y(tǒng)=bd(t)=min d(t), d (b) +a (b, t)=niin(8, 7+2|=8對(duì)點(diǎn)i及弧(d, 1)著色最終的最短路樹(shù)形圖由弧(

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

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