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