『壹』 最短路徑 | 深入淺出Dijkstra演算法（一）
上次我們介紹了神奇的只有 五行的 Floyd-Warshall 最短路演算法 ，它可以方便的求得 任意兩點的最短路徑， 這稱為 「多源最短路」。
這次來介紹 指定一個點（源點）到其餘各個頂點的最短路徑， 也叫做 「單源最短路徑」。 例如求下圖中的 1 號頂點到 2、3、4、5、6 號頂點的最短路徑。
與 Floyd-Warshall 演算法一樣，這里仍然 使用二維數組 e 來存儲頂點之間邊的關系， 初始值如下。
我們還需要用 一個一維數組 dis 來存儲 1 號頂點到其餘各個頂點的初始路程， 我們可以稱 dis 數組為 「距離表」， 如下。
我們將此時 dis 數組中的值稱為 最短路的「估計值」。
既然是 求 1 號頂點到其餘各個頂點的最短路程， 那就 先找一個離 1 號頂點最近的頂點。
通過數組 dis 可知當前離 1 號頂點最近是 2 號頂點。 當選擇了 2 號頂點後，dis[2]的值就已經從「估計值」變為了「確定值」， 即 1 號頂點到 2 號頂點的最短路程就是當前 dis[2]值。
為什麼呢？你想啊， 目前離 1 號頂點最近的是 2 號頂點，並且這個圖所有的邊都是正數，那麼肯定不可能通過第三個頂點中轉，使得 1 號頂點到 2 號頂點的路程進一步縮短了。 因此 1 號頂點到其它頂點的路程肯定沒有 1 號到 2 號頂點短，對吧 O(∩_∩)O~
既然選了 2 號頂點，接下來再來看 2 號頂點 有哪些 出邊 呢。有 2->3 和 2->4 這兩條邊。
先討論 通過 2->3 這條邊能否讓 1 號頂點到 3 號頂點的路程變短。 也就是說現在來比較 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 號頂點到 3 號頂點的路程，dis[2]+e[2][3]中 dis[2]表示 1 號頂點到 2 號頂點的路程，e[2][3]表示 2->3 這條邊。所以 dis[2]+e[2][3]就表示從 1 號頂點先到 2 號頂點，再通過 2->3 這條邊，到達 3 號頂點的路程。
我們發現 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新為 10。這個過程有個專業術語叫做 「鬆弛」 。即 1 號頂點到 3 號頂點的路程即 dis[3]，通過 2->3 這條邊 鬆弛成功。 這便是 Dijkstra 演算法的主要思想： 通過 「邊」 來鬆弛 1 號頂點到其餘各個頂點的路程。
同理通過 2->4（e[2][4]），可以將 dis[4]的值從 ∞ 鬆弛為 4（dis[4]初始為 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新為 4）。
剛才我們對 2 號頂點所有的出邊進行了鬆弛。鬆弛完畢之後 dis 數組為：
接下來，繼續在剩下的 3、4、5 和 6 號頂點中，選出離 1 號頂點最近的頂點。通過上面更新過 dis 數組，當前離 1 號頂點最近是 4 號頂點。此時，dis[4]的值已經從「估計值」變為了「確定值」。下面繼續對 4 號頂點的所有出邊（4->3，4->5 和 4->6）用剛才的方法進行鬆弛。鬆弛完畢之後 dis 數組為：
繼續在剩下的 3、5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 3 號頂點。此時，dis[3]的值已經從「估計值」變為了「確定值」。對 3 號頂點的所有出邊（3->5）進行鬆弛。鬆弛完畢之後 dis 數組為：
繼續在剩下的 5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 5 號頂點。此時，dis[5]的值已經從「估計值」變為了「確定值」。對5號頂點的所有出邊（5->4）進行鬆弛。鬆弛完畢之後 dis 數組為：
最後對 6 號頂點的所有出邊進行鬆弛。因為這個例子中 6 號頂點沒有出邊，因此不用處理。 到此，dis 數組中所有的值都已經從「估計值」變為了「確定值」。
最終 dis 數組如下，這便是 1 號頂點到其餘各個頂點的最短路徑。
OK，現在來總結一下剛才的演算法。 Dijkstra演算法的基本思想是：每次找到離源點（上面例子的源點就是 1 號頂點）最近的一個頂點，然後以該頂點為中心進行擴展，最終得到源點到其餘所有點的最短路徑。
基本步驟如下：
在 博客 中看到兩個比較有趣的問題，也是在學習Dijkstra時，可能會有疑問的問題。
當我們看到上面這個圖的時候，憑借多年對平面幾何的學習，會發現在「三角形ABC」中，滿足不了 構成三角形的條件(任意兩邊之和大於第三邊)。 納尼，那為什麼圖中能那樣子畫？
還是「三角形ABC」，以A為起點，B為終點，如果按照平面幾何的知識， 「兩點之間線段最短」， 那麼，A到B的最短距離就應該是6(線段AB)，但是，實際上A到B的最短距離卻是3+2=5。這又怎麼解釋？
其實，之所以會有上面的疑問，是因為 對邊的權值和邊的長度這兩個概念的混淆， 。之所以這樣畫，也只是為了方便理解（每個人寫草稿的方式不同，你完全可以用別的方式表示，只要便於你理解即可）。
PS：數組實現鄰接表可能較難理解，可以看一下 這里
參考資料：
Dijkstra演算法是一種基於貪心策略的演算法。每次新擴展一個路程最短的點，更新與其相鄰的點的路程。當所有邊權都為正時，由於不會存在一個路程更短的沒擴展過的點，所以這個點的路程永遠不會再被改變，因而保證了演算法的正確性。
根據這個原理， 用Dijkstra演算法求最短路徑的圖不能有負權邊， 因為擴展到負權邊的時候會產生更短的路徑，有可能破壞了已經更新的點路徑不會發生改變的性質。
那麼，有沒有可以求帶負權邊的指定頂點到其餘各個頂點的最短路徑演算法（即「單源最短路徑」問題）呢？答案是有的， Bellman-Ford演算法 就是一種。（我們已經知道了 Floyd-Warshall 可以解決「多源最短路」問題，也要求圖的邊權均為正）
通過 鄰接矩陣 的Dijkstra時間復雜度是 。其中每次找到離 1 號頂點最近的頂點的時間復雜度是 O(N)，這里我們可以用 優先隊列（堆） 來優化，使得這一部分的時間復雜度降低到 。這個我們將在後面討論。
『貳』 最短路徑演算法（Dijkstra）
Dijkstra（ 迪科斯特拉 ）演算法是用來解決核激唯單源最短路徑的演算法，要求路徑權值非負數。該演算法利用了深度優先搜索和貪心的演算法。
下面是一個有權圖，求從A到各個節點的最短路徑。
第1步：從A點出發，判斷每個點到A點的路徑（如果該點不能直連A點則距離值為無窮大，如果該點能和A直連則是當前的權值），計算完之後把A點上色，結果如下圖:
第2步：從除A點之外的點查找到距離A點最近的點C，從C點出發查找其鄰近的節點（除去已上色的點），並重新計算C點的鄰近點距離A點的值，如圖中B點，若新值（C點到A點的值+C點到該點的路徑）小於原值，則將值更新為5，同理更新D、E點。同時將C標鉛陵記為已經處理過，如圖所示塗色。
第3步：從上色的節點中查找距離A最近的B點，重復第3步操作。
第4步： 重復第3步，改培2步，直到所有的節點都上色。
最後就算出了從A點到所有點的最短距離。
leetcode 743題
『叄』 Dijkstra演算法流程圖
定義G=(V,E)，定義集合S存放已經找到最短路徑的頂點，集合T存放當前還未找到最短路徑的頂點，即有T=V-S
Dijkstra演算法描述如下：
(1) 假設用帶權的鄰接矩陣edges來表示帶權有向圖，edges[i][j]表示弧<Vi, Vj>上的權值。若<Vi, Vj>不存在則置edges[i][j]=∞（計算機上用一個允許的最大值代替）。S為已經找到的從Vs出發的最短路徑的終點集合，它初始化為空集。那麼，從Vs出發到圖上其餘各頂點（終點）Vi可能達到的最短路徑長度的初值為：D[i]=deges[s][i] Vi∈V
(2) 選擇Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是當前求得的一條從Vs出發的最短路徑的終點。令S=S∪{Vj}
(3) 修改從Vs出發到集合V-S上任一頂點Vk可達的最短路徑長度。如果D[j]+edges[j][k]<D[k]則修改D[k]為D[k]=D[j]+edges[j][k]
重復操作(2)(3)共n-1次。由此求得從Vs到圖上其餘各頂點的最短路徑。
『肆』 【數據結構】最短路徑之迪傑斯特拉(Dijkstra)演算法與弗洛伊德(Floyd)演算法
迪傑斯特拉(Dijkstra)演算法核心： 按照路徑長度遞增的次序產生最短路徑。
迪傑斯特拉(Dijkstra)演算法步驟：（求圖中v0到v8的最短路徑）並非一下子求出v0到v8的最短路徑，而是 一步一步求出它們之間頂點的最短路徑 ，過過程中都是 基於已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得出源點與終點的最短路徑 。
弗洛伊德(Floyd)演算法是一個經典的 動態規劃演算法 。