算法：
設(shè)G是帶權(quán)圖，圖中的頂點多于一個，且所有的權(quán)都為正數(shù)。本算法確定從頂點S到G中其他各個頂點的距離和最短通路。在本算法中P表示帶永久標(biāo)記的頂點的集合。頂點A的前驅(qū)是P中的一個頂點，用來標(biāo)記A。頂點U和V之間的邊的權(quán)重用W（U，V）表示，如果U和V之間沒有邊，則記作W(U,V)=∞.
步驟1 （對S做標(biāo)記）
（a）將S標(biāo)記為0，并使S沒有前驅(qū)
（b）令P={S}
步驟2 （對其他頂點作標(biāo)記）
將每個不在P中的頂點V標(biāo)記為W(S,V)(可能是暫時的），并使V的前驅(qū)為S（可能是暫時的）
步驟3 （擴大P，修改標(biāo)記）
Repeat
步驟3.1 （是另一個標(biāo)記永久化）
把不在P中且?guī)в凶钚?biāo)記的頂點U加入到P中去（如果這樣的頂點有多個則任選其中一個）
步驟3.2 （修改臨時標(biāo)記）
對每個不在P中并且和U相鄰的頂點X，把X的標(biāo)記替換為下列這兩者中的較小者：i)X的舊標(biāo)記,ii)U上的標(biāo)記與W（U，X）之和。如果X的標(biāo)記改變了，則使U成為X的新前驅(qū)（可能是暫時的）
Until P包含G中的每一個頂點
步驟4 （求出距離和最短通路）
頂點Y上的標(biāo)記是從S到Y(jié)的距離。如果Y上的標(biāo)記是∞，那么從S到Y(jié)就沒有通路，從而
沒有最短通路；否則，按照下列序列的逆序使用頂點就構(gòu)成從S到Y(jié)的一條最短通路：
Y，Y的前驅(qū)，Y的前驅(qū)的前驅(qū)，。。。。，直至S
證明：Dijkstra算法給出了從S到G的各個頂點的最短通路長度。
我們假設(shè)Ｇ中的每個頂點Ｖ都被賦予了一個標(biāo)記L(V),它要么是一個數(shù)，要么是∞。假設(shè)P是G的頂點的集合，P包含S，滿足：
1）如果V屬于P，則L（V）是從S到V的最短通路的長度，并且存在這樣的從S到V的最短通路：通路上的頂點都在P中
2）如果V不屬于P，則L(V)是從S到V的滿足下面限制的最短通路的長度：V是通路中唯一一個不屬于P的頂點。
我們可以用歸納法證明Dijkstra算法中的P符合上述定義的集合：
1）當(dāng)P中元素個數(shù)為1時，P對應(yīng)算法中的第一步，P={S},顯然滿足。
2）假設(shè)P中元素個數(shù)為K時，P滿足上述定義，下面看算法的的第三步，
先找出不在P中且?guī)в凶钚?biāo)記的頂點U，標(biāo)記為L(U), 可以證明從S到U的最短通路中除U外不包含不屬于P的元素。
因為若存在除U外其他頂點，則最短通路為SP1P2...PnQ1Q2...QnU(P1,P2..Pn屬于P,Q1,Q2,...Qn不屬于P),則由性質(zhì)2）最短通路長度為L(Q1)+PATH(Q1,U)>L(U)
從而大于SP1P2..PnU的通路長度L(U)，不是最短通路，所以從S到U的最短通路中除U外不包含不屬于P的元素，從而從S到U的最短通路長度由L(U)給出.
現(xiàn)把U加入P中構(gòu)成P' ,顯然P'滿足性質(zhì)1)。
取V不屬于P',顯然V也不屬于P,那么從S到V的最短通路且滿足除V外所有頂點都在P'中的通路有兩種可能，i）包含U，ii）不包含U。
對i）SP1P2...PnUV=L(U)+W(U,V)
ii)SP1P2..PnV=L(V)
顯然二者中的最小給出了從S到V的最短通路且滿足除V外所有頂點都在P'中的長度。
從而算法第三步給出的P'含K+1個元素且滿足1),2)。
又歸納，命題得證！
下面是一個Java版的實現(xiàn):最短路徑的Java實現(xiàn)