迪杰斯特拉算法用于求解一個(gè)有向圖（也可以是無向圖,無向圖是有向圖的一種特例）的一個(gè)點(diǎn)（稱之為原點(diǎn)）到其余各點(diǎn)（稱之為周邊點(diǎn)）的最短路徑問題.算法構(gòu)思很是巧妙（我這么認(rèn)為）,簡(jiǎn)直達(dá)到了“無心插柳柳成蔭”的境界.算法本身并不是按照我們的思維習(xí)慣——求解從原點(diǎn)到第一個(gè)點(diǎn)的最短路徑,再到第二個(gè)點(diǎn)的最短路徑,直至最后求解完成到第n個(gè)點(diǎn)的最短路徑,而是求解從原點(diǎn)出發(fā)的各有向路徑的從小到大的排列（如果這個(gè)有向圖中有環(huán)1-2-3-1算法豈不是永無終結(jié)之日了?!）,但是算法最終確實(shí)得到了從原點(diǎn)到圖中其余各點(diǎn)的最短路徑,可以說這是個(gè)副產(chǎn)品,對(duì)于算法的終結(jié)條件也應(yīng)該以求得了原點(diǎn)到圖中其余各點(diǎn)的最短路徑為宜.清楚了算法的這種巧妙構(gòu)思后,理解算法本身就不是難題了.
算法把一個(gè)圖（G）中的點(diǎn)劃分成了若干部分：
1）：原點(diǎn)（v）；
2）：所有周邊點(diǎn)（C）；
另外有一個(gè)輔助集合S,從v到S中的點(diǎn)的最短路徑已經(jīng)求得.S的最初狀態(tài)是空集.
這樣就可以進(jìn)一步劃分圖（G）：
1）：原點(diǎn)（v）；
2）：已求出v至其最短路徑的周邊點(diǎn)（S）；
3）：尚未求出v至其最短路徑的周邊點(diǎn)（Other=C-S）；
算法的主體思想：
A、找到v——Other所有路徑中的的最短路徑vd=v——d（Other的一個(gè)元素）；
B、找到v——S——Other所有路徑中的的最短路徑vi=v——i（Other的一個(gè)元素）；
C、比較vd和vi如果vd