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