Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家艾茲格·迪科斯徹發(fā)現(xiàn)的。算法解決的是有向圖中最短路徑問(wèn)題。
舉例來(lái)說(shuō)，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示著城市間開(kāi)車(chē)行經(jīng)的距離。 Dijkstra算法可以用來(lái)找到兩個(gè)城市之間的最短路徑。
Dijkstra算法的輸入包含了一個(gè)有權(quán)重的有向圖G，以及G中的一個(gè)來(lái)源頂點(diǎn)S。 我們以V表示G中所有頂點(diǎn)的集合。圖中的每一個(gè)邊，都是兩個(gè)頂點(diǎn)所形成的有序元素對(duì)。(u,v)表示從頂點(diǎn)u到v有路徑相連。 假設(shè)E為所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)w: E → [0, ∞]定義。 因此，w(u,v)就是從頂點(diǎn)u到頂點(diǎn)v的非負(fù)花費(fèi)值(cost)。 邊的花費(fèi)可以想像成兩個(gè)頂點(diǎn)之間的距離。任兩點(diǎn)間路徑的花費(fèi)值，就是該路徑上所有邊的花費(fèi)值總和。 已知有V中有頂點(diǎn)s及t，Dijkstra算法可以找到s到t的最低花費(fèi)路徑(i.e. 最短路徑)。 這個(gè)算法也可以在一個(gè)圖中，找到從一個(gè)頂點(diǎn)s到任何其他頂點(diǎn)的最短路徑。
算法描述
這個(gè)算法是通過(guò)為每個(gè)頂點(diǎn)v保留目前為止所找到的從s到v的最短路徑來(lái)工作的。初始時(shí)，源點(diǎn)s的路徑長(zhǎng)度值被賦為0（d[s]=0）， 同時(shí)把所有其他頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大，即表示我們不知道任何通向這些頂點(diǎn)的路徑（對(duì)于V中所有頂點(diǎn)v除s外d[v]= ∞）。當(dāng)算法結(jié)束時(shí)，d[v]中儲(chǔ)存的便是從s到v的最短路徑，或者是無(wú)窮大（如果路徑不存在的話）。
Dijstra算法的基礎(chǔ)操作是邊的拓展：如果存在一條從u到v的邊，那么從s到v的最短路徑可以通過(guò)將邊(u,v)添加到s到u的尾部來(lái)拓展。這條路徑的長(zhǎng)度是d[u]+w(u,v)。如果這個(gè)值比目前已知的d[v]的值要小，我們可以用新值來(lái)替代當(dāng)前d[v]中的值。拓展邊的操作一直執(zhí)行到所有的d[v]都代表從s到v最短路徑的花費(fèi)。這個(gè)算法經(jīng)過(guò)適當(dāng)?shù)慕M織因而當(dāng)d[u]達(dá)到它最終的值的時(shí)候，每條邊(u,v)都只被拓展一次。
算法維護(hù)兩個(gè)頂點(diǎn)集S和Q。集合S保留了我們已知的所有d[v]的值已經(jīng)是最短路徑的值頂點(diǎn)，而集合Q則保留其他所有頂點(diǎn)。集合S初始狀態(tài)為空，而
后每一步都有一個(gè)頂點(diǎn)從Q移動(dòng)到S。這個(gè)被選擇的頂點(diǎn)是Q中擁有最小的d[u]值的頂點(diǎn)。當(dāng)一個(gè)頂點(diǎn)u從Q中轉(zhuǎn)移到了S中，算法對(duì)每條外接邊(u,v)進(jìn)
行拓展。
算法思想
設(shè)S為最短距離已確定的頂點(diǎn)集（看作紅點(diǎn)集），V-S是最短距離尚未確定的頂點(diǎn)集（看作藍(lán)點(diǎn)集）。
①初始化
初始化時(shí)，只有源點(diǎn)s的最短距離是已知的(SD(s)=0)，故紅點(diǎn)集S={s}，藍(lán)點(diǎn)集為空。
②重復(fù)以下工作，按路徑長(zhǎng)度遞增次序產(chǎn)生各頂點(diǎn)最短路徑
在當(dāng)前藍(lán)點(diǎn)集中選擇一個(gè)最短距離最小的藍(lán)點(diǎn)來(lái)擴(kuò)充紅點(diǎn)集，以保證按路徑權(quán)重遞增的次序來(lái)產(chǎn)生各頂點(diǎn)的最短路徑。
當(dāng)藍(lán)點(diǎn)集中僅剩下最短距離為∞的藍(lán)點(diǎn)，或者所有藍(lán)點(diǎn)已擴(kuò)充到紅點(diǎn)集時(shí)，s到所有頂點(diǎn)的最短路徑就求出來(lái)了。
注意：
①若從源點(diǎn)到藍(lán)點(diǎn)的路徑不存在，則可假設(shè)該藍(lán)點(diǎn)的最短路徑是一條長(zhǎng)度為無(wú)窮大的虛擬路徑。
?、趶脑袋c(diǎn)s到終點(diǎn)v的最短路徑簡(jiǎn)稱(chēng)為v的最短路徑；s到v的最短路徑長(zhǎng)度簡(jiǎn)稱(chēng)為v的最短距離，并記為SD(v)。
（3）在藍(lán)點(diǎn)集中選擇一個(gè)最短距離最小的藍(lán)點(diǎn)k來(lái)擴(kuò)充紅點(diǎn)集
根據(jù)按長(zhǎng)度遞增序產(chǎn)生最短路徑的思想，當(dāng)前最短距離最小的藍(lán)點(diǎn)k的最短路徑是：
源點(diǎn)，紅點(diǎn)1，紅點(diǎn)2，…，紅點(diǎn)n，藍(lán)點(diǎn)k
距離為：源點(diǎn)到紅點(diǎn)n最短距離+<紅點(diǎn)n,藍(lán)點(diǎn)k>邊長(zhǎng)
為求解方便，設(shè)置一個(gè)向量D[0．．n-1]，對(duì)于每個(gè)藍(lán)點(diǎn)v∈ V-S，用D[v]記錄從源點(diǎn)s到達(dá)v且除v外中間不經(jīng)過(guò)任何藍(lán)點(diǎn)(若有中間點(diǎn)，則必為紅點(diǎn))的"最短"路徑長(zhǎng)度（簡(jiǎn)稱(chēng)估計(jì)距離）。
若k是藍(lán)點(diǎn)集中估計(jì)距離最小的頂點(diǎn)，則k的估計(jì)距離就是最短距離，即若D[k]=min{D[i]
i∈V-S}，則D[k]=SD(k)。
初始時(shí)，每個(gè)藍(lán)點(diǎn)v的D[c]值應(yīng)為權(quán)w<s，v>，且從s到v的路徑上沒(méi)有中間點(diǎn)，因?yàn)樵撀窂絻H含一條邊<s，v>。
注意：
在藍(lán)點(diǎn)集中選擇一個(gè)最短距離最小的藍(lán)點(diǎn)k來(lái)擴(kuò)充紅點(diǎn)集是Dijkstra算法的關(guān)鍵
（4）k擴(kuò)充紅點(diǎn)集s后，藍(lán)點(diǎn)集估計(jì)距離的修改
將k擴(kuò)充到紅點(diǎn)后，剩余藍(lán)點(diǎn)集的估計(jì)距離可能由于增加了新紅點(diǎn)k而減小，此時(shí)必須調(diào)整相應(yīng)藍(lán)點(diǎn)的估計(jì)距離。
對(duì)于任意的藍(lán)點(diǎn)j，若k由藍(lán)變紅后使D[j]變小，則必定是由于存在一條從s到j(luò)且包含新紅點(diǎn)k的更短路徑：P=<s，…，k，j>。且D
[j]減小的新路徑P只可能是由于路徑<s，…，k>和邊<k，j>組成。
所以，當(dāng)length(P)=D[k]+w<k，j>小于D[j]時(shí)，應(yīng)該用P的長(zhǎng)度來(lái)修改D[j]的值。
（5）Dijkstra算法
Dijkstra(G，D，s){
//用Dijkstra算法求有向網(wǎng)G的源點(diǎn)s到各頂點(diǎn)的最短路徑長(zhǎng)度
//以下是初始化操作
S={s}；D[s]=0； //設(shè)置初始的紅點(diǎn)集及最短距離
for( all i∈ V-S )do //對(duì)藍(lán)點(diǎn)集中每個(gè)頂點(diǎn)i
D[i]=G[s][i]； //設(shè)置i初始的估計(jì)距離為w<s，i>
//以下是擴(kuò)充紅點(diǎn)集
for(i=0;i<n-1;i++)do{//最多擴(kuò)充n-1個(gè)藍(lán)點(diǎn)到紅點(diǎn)集
D[k]=min{D[i]：all i V-S}； //在當(dāng)前藍(lán)點(diǎn)集中選估計(jì)距離最小的頂點(diǎn)k
if(D[k]等于∞)
return； //藍(lán)點(diǎn)集中所有藍(lán)點(diǎn)的估計(jì)距離均為∞時(shí)，
//表示這些頂點(diǎn)的最短路徑不存在。
S=S∪{k}； //將藍(lán)點(diǎn)k涂紅后擴(kuò)充到紅點(diǎn)集
for( all j∈V-S )do //調(diào)整剩余藍(lán)點(diǎn)的估計(jì)距離
if(D[j]>D[k]+G[k][j])
//新紅點(diǎn)k使原D[j]值變小時(shí)，用新路徑的長(zhǎng)度修改D[j]，
//使j離s更近。
D[j]=D[k]+G[k][j]；
}
}