最短路徑算法Dijkstra歸納

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

2、有節(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,CLOSE表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式。注意

3、該算法要求圖中不存在負(fù)權(quán)邊。算法描述(這里描述的是從節(jié)點(diǎn)1開始到各點(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 +無窮大(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)集合V分成兩

4、組，第一組為已求出最短路徑的頂點(diǎn)集合(用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑就將 加入到集合 S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了)，第二組為其余未確定最短路徑的頂點(diǎn)集合(用 U表示)，按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn) v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v至U 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包含

5、除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)過頂點(diǎn)k）比原來距離（不經(jīng)過頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。（4）重復(fù)步驟（2）和（3）直到所有頂點(diǎn)都包含在S中。復(fù)雜度分析Dijkstra 算法的時(shí)間復(fù)雜度為0（n A2）空間復(fù)雜度取決于存儲(chǔ)方式，鄰接矩陣為O（ nT）Dijkstra 算法迪杰斯特拉（Dijks

6、t2）笄法是單源瑣點(diǎn)驚短略徑求解算江木例以"結(jié)點(diǎn)（1匕結(jié)點(diǎn)）為計(jì)算源.有向圖與鄰接矩陣:有向網(wǎng)絡(luò)123451f010g30too2g050g3O>0»104«200605O08-OO80鄰接矩陣算法的動(dòng)態(tài)執(zhí)行情況表格中的項(xiàng)目說明:1.循環(huán):執(zhí)fir咒法的次數(shù)/2、源二通過運(yùn)算厲，當(dāng)前己綾加入的結(jié)點(diǎn)is K+1：本次運(yùn)算新加入的結(jié)點(diǎn)口4、冃的結(jié)點(diǎn)開銷：從源結(jié)點(diǎn)到冃的結(jié)點(diǎn)最優(yōu)路徉的開銷5、甬耶結(jié)點(diǎn)；所冇結(jié)血按風(fēng)最優(yōu)路彳#逆冋到W結(jié)點(diǎn)的上個(gè)結(jié)點(diǎn)#精環(huán)K+1目的第點(diǎn)開帝麗匏結(jié)點(diǎn)17.34S123斗5初始化1*0103010001011步 1:運(yùn)算過程：i| J HP

7、1 1'.'.l' Kt. 1 V3. '' rjVI "J f'l V3,從也到込口的個(gè)結(jié)點(diǎn)是¥1卿収境嘩V3無袪將謝”哉祝告燈【VI。從有向團(tuán)屮可以看出VI4白 已吿知給VL必銀通過V2>怛是V2 還沒有進(jìn)入中*即當(dāng)前數(shù)振庫(kù)中 沒到達(dá)VI的相關(guān)信息炳以叫將視為 到詢不可達(dá)，填m血韜環(huán)目的錯(cuò)點(diǎn)開銷前驅(qū)結(jié)點(diǎn)123斗512345初始化1010max30100010111L2I2010603010001211翊2：得加入節(jié)虐晝V2, VI, V4 V5 從冇向圖中看肌從VI略直可直桎 至噠的結(jié)戊分別是VT V4, VS.VI

8、 V2,開銷:1071 j'lj V4+ h ffi： 30VI到V5*開銷土 100 將JI銷簞小的弟點(diǎn)卻入到源中.JM1入罔的i_L知書點(diǎn)士 VI, V2 由于已經(jīng)將V2加入和亟中所 U此時(shí)VI戟可以通過V2別達(dá) V3獲知從VI和達(dá)V*的稱樸為:VI -> V2 V3 7KH： 60 將開銷由rnat墳寫為60 此時(shí)VI叮以到達(dá)V3.塵路觸 序塾VI今2今V3從VI逆捋.則g的前驅(qū)是 曲所以將以前o«r(r段寫 為y循環(huán)K+1目叫皓點(diǎn)開銷前第結(jié)點(diǎn)1234512345初始化1010max3010001a111(U)2010603D1D00111121-2.440105

9、03010001411轉(zhuǎn)加入節(jié)心土 V3. V4, V5加入潔的已知節(jié)盤:VI. V2. V4Ml匕經(jīng)槪級(jí)入。剛以本次押除對(duì)*2蜩2中.viflva的路繪知伯計(jì)畀.當(dāng)前可迖鈕躋有：VI -? V2 -> V3，幵稍為 60。Hi肖：曲此撫由于加入了所以VI到VI -* V4,幵*乩 30V3闊晞?shì)p為VI -> V5 H簡(jiǎn)：100VI -> V7 -* V3,開捎為 F0.VI -> V2->VS+ 刃制：60/1 V4 -> V3，開巒為 5S將Xtfl圮小的站心加入到源屮3將曲舒史新為開陽(yáng)更小的路民從VitlJitVS的最優(yōu)路 卷已經(jīng)被更新為:VI V4

10、V3V3!勺沁嘔為皿搐此 處佯宦夢(mèng)為亠礦歩驟4；循環(huán)源K+1目的結(jié)點(diǎn)開悄前奧姑點(diǎn)1234512345初始化1010max301000101113】20106030100012112仏石叫40105030100141131JA330105030&001413訃加入節(jié)點(diǎn)：心V5目前圖屮的所有苛Ht畀的路樓: 壯m.卄討：V4r->V1.'- 30VI V5. ”刖卜 100VI V2 V3.升柄 G0VI今”4今V3、開鈿50Vl V2-> V3-> V5，開悄；60 勺丄今W >歸今V5.丿I悄：60 務(wù)幵銷最小的酷點(diǎn)加人到源中.加I上斤的已知節(jié)點(diǎn)土 VI

11、, V2. V4 比無前kVlf'JVS的毬珞爍 此次加入了 V3.存在更憂蹄錘 VI V4 -> V3 -> V5 刃銷：60 史拓丿I銷*60.最優(yōu)路牡改變.更新 為最優(yōu)踣輕的前鼎士戲5：ts環(huán)遁K+l目的第點(diǎn)開銷前縣辭點(diǎn)1234£12345初始化010mex3010C0i01111.22D1060北100012112(1X4)401050301000i411312-433010503(60014141JA3.55010503060ni41持加入節(jié)點(diǎn)：V5加入V5當(dāng)前到詳?shù)拿芫τ小縑I >VST !| 桶：100VI ->V4->V5，Jl

12、lfl： 90VI ->V4 ->V3 -> V5，/HH： 60優(yōu)地+1磐為so的最短路的算法-一Dijkstra算法在圖仟中，給圮苦和t兩個(gè)頂4從制到t可以冇多條路彳#從這名條略中找出長(zhǎng)度嚴(yán) 小的路，這樣的路稱為從百到t的最短路。設(shè)每條孤的長(zhǎng)度均為非負(fù)值*卜面的算法是由狄克期待拉(Dijtra, 195«提出的，英想法是：設(shè)已知圖中最接近 于頂點(diǎn)s旳m個(gè)頂點(diǎn)以及從頂點(diǎn)出到這些加點(diǎn)中每一個(gè)頂點(diǎn)的最您路(從s到其本口的最短 路是零路，即沒冇弧的路，HKJ&為0人對(duì)頂點(diǎn)£和這川個(gè)頂點(diǎn)看色。然民 最接近丁飛 的第血I牛頂點(diǎn)W如卜求之：匕對(duì)于毎一個(gè)未著色

13、的唄點(diǎn)V,枝慮所冇已著色頂點(diǎn)X,把弧g y)接在從s到x的最 短路后面.這樣就得到從s乳y的m條不同路。從這圍條路中選出最短的路，它就是從s 到y(tǒng)的最短路理曲的y點(diǎn)就址最接近T s的豹時(shí)1個(gè)頂點(diǎn)凋?yàn)樗鶅踊〉拈L(zhǎng)度祁繪非負(fù)佻 所以從只到最接近于s的第時(shí)1個(gè)頂點(diǎn)的最扳路必然!H使用已著色的頂點(diǎn)作曲中間頂點(diǎn)。從m-0卄始，將這個(gè)過桎重復(fù)進(jìn)行卜去，宜至求得從5 f( t的星短路為止。算法；狄克斯特拉最短路算法第1步開始*所冇弧和頂點(diǎn)都未著匕 對(duì)每個(gè)頂點(diǎn)x指加 個(gè)數(shù) H d&)表示從百到， 的最短路的長(zhǎng)度(中間頂點(diǎn)均已著色人開始時(shí)，令d(s)-D, d(Q8 對(duì)所有好幾、表 示已著色的昂后 個(gè)頂點(diǎn)

14、，對(duì)始點(diǎn)用著色令廠頭第2步対于釘個(gè)未著色頂點(diǎn)禺 遺新芒義d(Q如卜1d(x)min d(x) d (y)+a(y, x)公式剤丁所冇耒著色頂點(diǎn)血 如肛小二8,則算法繆仁 因?yàn)榇藭r(shí)從卻到任一未若色的頂點(diǎn)祁沒 冇踰 否虬 対H冇d(x)M小值的朱看色頂點(diǎn)k進(jìn)行著色也同吋耙弧(廠衛(wèi)著色指向頂 點(diǎn)乂的弧只冇條彼肴色九令y二壯第3步 如果頂點(diǎn)t已前色，如焼濃終此 這時(shí)已找到一條從占到I的憬勿路如果t未著 色則轉(zhuǎn)笫2步，注意：已看色的狐不能構(gòu)成 個(gè)圈而是構(gòu)成一個(gè)根左s的WttJIS，此樹形圖稱為顯愆路樹 形鄭若X是最短路稠形圖中的任一頂點(diǎn)，則從S到X的唯一的一條路繪從S到X的最短路. 這個(gè)算法可以看成是根

15、在頂點(diǎn)s的樹形圖的生懺過禪。一旦到達(dá)頂點(diǎn)S生長(zhǎng)過程就停|上。 例：給沱冇向團(tuán)釦卜圖所示，用狄克斯特拉養(yǎng)注找出從*劍L的雖短路從訊2步y(tǒng)-sd(a)=mir I d(a)t d (s)+a(s, a) I=min «, 0+4 = 1d(b)-iriin d(b) t d (s)+a(s, b)=min°°± 0+71 _7d(c)=win d(c), d (s) +a(st r) |=mi n («>* 0+3 =3d(d)=min ( d(d), d(s) +h(s, d)=mi n 3, (1+e =8d (t)=min d(t),

16、d(s)+a(s, t)=min *>, 0 卜 8)=«由于d(<:)<5是呆小值，所以對(duì)c點(diǎn)著色.并對(duì)確d(c)的弧&匚)希色。見圖枝)。第3頂點(diǎn)I木看色，返冋第2 5Ka)第2步y(tǒng)=cd(a) win I cf (a). cf (r)+a (c, a) *=uinf4,3+ =4d(h)nnin d(h) t d(c)+n(rt b)=minf7t3«*=7d(d) f d(d), d(r)+nG'p d)-mi ii 3+3 -6d(t) =min( d(t), d(c)+aCe, t)-min («, 3+oa =w&g

17、t;由于dfa=4是最小值,所以對(duì)頂點(diǎn)拭著色.井對(duì)確id<a)的弧a)著色。見閤b駡弟3步頂點(diǎn)1未看色.返何第2歩.b)第2步y(tǒng)pd(b) =min d(t»), TO 十&仏Ij"-min 17,4+3-7d(d)=min d(d), d(a) +a (o, d)：=min& 4+2)-6d(t)=inin ( d(t), d(a) +a(a, t)=min (w. 4 =«?d(d)=fl是颯小值,對(duì)M著色,確宦Kd)的弧青胸條(即(cd)和(a.d),可枉選其中的 余對(duì)其著色，我們選(C1d)4見圖cA第3步頂點(diǎn)t未著性，返冋第2步；第

18、2步尸dd(b) =uia d(b)r d(d)-*a(d, b)二Enin (7,6+°° -7d(t)=inin d(t)j d(d)+a(dft)二mi n g, 6+2 -8d(b)=7是最小值.對(duì)點(diǎn)b著色,對(duì)確定d(b)的弧ah)著色。見圖dh 第3步 頂點(diǎn)t未*色，返冋第2步.第2涉/=bd(t)=nin d(t), d(b)+o(b, i)=minBf 7+2 =8對(duì)點(diǎn)l叢弧t)著色.鍛終的最短路樹形圖由弧c) (s, h)(d) (s, h)和(d. t) 細(xì)成*見e)Dijkstra算法的基本思想是:設(shè)U的節(jié)點(diǎn)就構(gòu)造SPFPHl占，址根節(jié)點(diǎn)為e 任條謹(jǐn)略"丿）的長(zhǎng)頂為百. 毎個(gè)節(jié)點(diǎn)到Jt的般矩路屋長(zhǎng)度怙計(jì)為定義所育廿點(diǎn)的卑合hA.宦義集合PAt 井設(shè)定集ft P的忸始值為P斗母0況算法迭代的過慳中如杲已經(jīng)變成一今確迢值，則將j標(biāo)詁為固宦點(diǎn)，并猖英加 入年合I 在訐也的耶一眇迭代中.在尸以外的節(jié)點(diǎn)中必定足選擇與口的節(jié)點(diǎn)氏曲近的 廿點(diǎn)加入到嚴(yán)中.算法的具悴步驟如下：芒< ）P二舊*比=乩°卅="代j丘P t若）和&不是相鄰