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