版權聲明：本文為部落客原創文章，轉載請注明出處。 https://blog.csdn.net/leaf_130/article/details/50668868
在圖形應用中，常常需要求從圖中某個結點至其餘各結點的最短路徑，如對于一個物流配送系統計算從配送中心到各訂貨點的最短路徑。
Dijkstra's Algorithm 基本思想：
若給定帶權有向圖G=(V,E)和源頂點v0，構築一個源集合S，将v0加入其中。
① 對差集V\S中 個頂點vi，逐一計算從v0 至它的距離 D(v0 , vi ),若該兩頂點之間沒有邊，則其距離為無窮大。求出其中距離最短 的頂點w，将其加入到集合 S 中。
② 重新計算 v0 至差集 V\S 中各頂點的距離 D（v0, vi ）= Min(D(v0, vi ), D(v0, w ) + C(w, vi )).其中C（w, vi ）是頂點w 與 vi 之 間邊上的費用。
③ 重複 步驟①②。直至所有的頂點都加到集合S 中為止。
算法求解過程圖式：
把該圖看成是物流配送系統，邊上的數字是各地間距離，配送中心位于結點1處，根據該算法就可以設計出從結點 1 至其他各個結點線路最短的配送線路。
步驟：
小結：
Dijkstra's 算法與最小生成樹的差別在于：
① 最小生成樹是對全圖而言的，而Dijkstra's算法是對某個結點而言的。
② 最小生成樹是連接配接所有結點的最短路徑，但是如果從某個結點出發，沿着最小生成樹到另一個結點的路徑不一定是最短的。 而在Dijkstra's樹中，從根結點到各葉子結點的路徑都是最短的。
③ 若Dijkstra's算法依次應用于每個頂點，最後可以得到任意兩個頂點之間的最短路徑，這就是通常所說的任意頂點對之間的最短路徑問題（all-pairs shortest paths,APAP）
ps:Floyd算法也是求解這類問題的算法。