今天晚上學(xué)習(xí)了這個算法，看了網(wǎng)上的好些資料，用自己的理解記錄下來。
Dijkstra算法是由荷蘭計算機(jī)科學(xué)家艾茲格·迪科斯徹發(fā)現(xiàn)的。算法解決的是有向圖或無向圖中最短路徑問題。
算法描述：
?????????這個算法是通過為每個頂點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到u的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到v的路徑。這條路徑的長度是d[u]+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當(dāng)前d[v]中的值。拓展邊的操作一直執(zhí)行到所有的d[v]都代表從s到v最短路徑的花費(fèi)。這個算法經(jīng)過組織因而當(dāng)d[u]達(dá)到它最終的值的時候沒條邊(u,v)都只被拓展一次。
算法流程：
1. 在算法中每個結(jié)點中都進(jìn)行標(biāo)注，標(biāo)注分為臨時性標(biāo)注和永久性標(biāo)注；
2.初始時，所有結(jié)點都為臨時性標(biāo)注，標(biāo)注值為無窮大；
3.將源結(jié)點標(biāo)注為0，且為永久性標(biāo)注，并令其為工作結(jié)點；
4.檢查與工作結(jié)點相鄰并標(biāo)注為臨時標(biāo)注的結(jié)點，若該結(jié)點到工作結(jié)點的距離與工作結(jié)點的標(biāo)注之和小于該結(jié)點的標(biāo)注，則用新計算得到的和重新標(biāo)注該結(jié)點，并將工作結(jié)點記錄為該結(jié)點的上一結(jié)點；
5.在整個圖中查找具有最小值的臨時性標(biāo)注結(jié)點，將其變?yōu)橛谰眯越Y(jié)點，并成為下一輪檢查的工作結(jié)點；
重復(fù)第四、五步，直到目的結(jié)點成為工作結(jié)點。這時目標(biāo)結(jié)點中的標(biāo)注值就是目標(biāo)結(jié)點到源結(jié)點的最短路徑值。而回溯各結(jié)點的上一結(jié)點直到源結(jié)點。就是最短路徑。
示例：
文章資源來源于：
1. http://www.roboticfan.com/college/knowledge/200608/195.shtml
2. http://johnfat.bokee.com/3435427.html