基本定義
Dijkstra(迪傑斯特拉)算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業課程中都作為基本内容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時标号方式，一種是用OPEN,CLOSE表的方式，這裡均采用永久和臨時标号的方式。注意該算法要求圖中不存在負權邊。
原理
1.首先，引入一個輔助向量D，它的每個分量D[i]表示當前所找到從起始點v（即點V）到其他每個定點vi的長度。
例如，D[3]=2表示從起始點到頂點3的路徑相對最小長度為2。這裡強調相對就是說在算法執行過程中D的值是在不斷逼近最終結果但在過程中不一定就等于長度。
2.D的初始狀态為：若從v到v1有弧（即從v到vi存在連接邊），則D[i]為弧上的權值（即為從v到vi的邊的權值）；否則置D[i]為∞。
顯然，長度為D[j]=Min{D|vi∈V}的路徑就是從v出發到頂點vj的長度最短的一條路徑，此路徑為(v,vj)。
3.那麼，下一條長度次短的是哪一條呢？也就是找到從源點v到下一個頂點的最短路徑長度所對應的頂點，且這條最短路徑長度僅次于從源點v到頂點vj的最短路徑長度。
假設該次短路徑的終點是vk，則可想而知，這條路徑要麼是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權值，或者是D[j]加上從vj到vk的弧上的權值。
4.一般情況下，假設S為已求得的從源點v出發的最短路徑長度的頂點的集合，則可證明：下一條次最短路徑（設其終點為x）要麼是弧(v,x)，或者是從源點v出發的中間隻經過S中的頂點而最後到達頂點x的路徑。
因此，下一條長度次短的的最短路徑長度必是D[j]=Min{D[i]vi∈V-S}，其中D[i]要麼是弧(v,vi)上的權值，或者是D[k]vk(∈S)和弧(vk,vi)上的權值之和。
算法描述如下：
1）令arcs表示弧上的權值。若弧不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到的從v出發的的終點的集合，初始狀态為空集。那麼，從v出發到圖上其餘各頂點vi可能達到的長度的初值為D=arcs[LocateVex(G,vi]，vi∈V；
2）選擇vj，使得D[j]=Min{D|vi∈V-S}；
3）修改從v出發的到集合V-S中任一頂點vk的最短路徑長度。
問題描述
在無向圖G=(V,E)中，假設每條邊E[i]的長度為w[i]，找到由頂點V0到其餘各點的最短值。
算法思想
按路徑長度遞增次序産生算法：
把頂點集合V分成兩組：
（1）S：已求出的頂點的集合（初始時隻含有源點V0）
（2）V-S=T：尚未确定的頂點集合
将T中頂點按遞增的次序加入到S中，保證：
（1）從源點V0到S中其他各頂點的長度都不大于從V0到T中任何頂點的最短路徑長度
（2）每個頂點對應一個距離值
S中頂點：從V0到此頂點的長度
T中頂點：從V0到此頂點的隻包括S中頂點作中間頂點的最短路徑長度
依據：可以證明V0到T中頂點Vk的，或是從V0到Vk的直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和
（反證法可證）
求最短路徑步驟
算法步驟如下：
G={V,E}
1.初始時令S={V0},T=V-S={其餘頂點}，T中頂點對應的距離值
若存在，d(V0,Vi)為弧上的權值
若不存在，d(V0,Vi)為∞
2.從T中選取一個與S中頂點有關聯邊且權值最小的頂點W，加入到S中
3.對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值
重複上述步驟2、3，直到S中包含所有頂點，即W=Vi為止
堆優化
思考
該算法複雜度為n^2,我們可以發現，如果邊數遠小于n^2,對此可以考慮用堆這種數據結構進行優化，取出最短路徑的複雜度降為O(1)；每次調整的複雜度降為O（elogn）；e為該點的邊數，所以複雜度降為O((m+n)logn)。
實現
1.将與源點相連的點加入堆，并調整堆。
2.選出堆頂元素u（即代價最小的元素），從堆中删除，并對堆進行調整。
3.處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點。
1):若該點在堆裡，更新距離，并調整該元素在堆中的位置。
2):若該點不在堆裡，加入堆，更新堆。
4.若取到的u為終點，結束算法；否則重複步驟2、3。
