dijkstra的單源最短路徑演算法

『壹』 最短路徑演算法（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演算法

最短路徑問題是圖論研究中一個經典演算法問題，旨在尋找圖中兩節點或單個節點到其他節點之間的最短路徑。根據問題的不同，演算法的具體形式包括：

常用的最短路徑演算法包括：Dijkstra演算法，A 演算法，Bellman-Ford演算法，SPFA演算法（Bellman-Ford演算法的改進版本），Floyd-Warshall演算法，Johnson演算法以及Bi-direction BFS演算法。本文將重點介紹Dijkstra演算法的原理以及實現。

Dijkstra演算法，翻譯作戴克斯特拉演算法或迪傑斯特拉演算法，於1956年由荷蘭計算機科學家艾茲赫爾.戴克斯特拉提出，用於解決賦權有向圖的 單源最短路徑問題 。所謂單源最短路徑問題是指確定起點，尋找該節點到圖中任意節點的最短路徑，演算法可用於尋找兩個城市中的最短路徑或是解決著名的旅行商問題。

問題描述 ：在無向圖 中， 為圖節點的集合， 為節點之間連線邊的集合。假設每條邊 的權重為 ，找到由頂點 到其餘各個節點的最短路徑（單源最短路徑）。

為帶權無向圖，圖中頂點 分為兩組，第一組為已求出最短路徑的頂點集合（用 表示）。初始時 只有源點，當求得一條最短路徑時，便將新增頂點添加進 ，直到所有頂點加入 中，演算法結束。第二組為未確定最短路徑頂點集合（用 表示），隨著 中頂點增加， 中頂點逐漸減少。

以下圖為例，對Dijkstra演算法的工作流程進行演示（以頂點 為起點）：

註：
01） 是已計算出最短路徑的頂點集合；
02） 是未計算出最短路徑的頂點集合；
03） 表示頂點 到頂點 的最短距離為3
第1步 ：選取頂點 添加進

第2步 ：選取頂點 添加進 ，更新 中頂點最短距離

第3步 ：選取頂點 添加進 ，更新 中頂點最短距離

第4步 ：選取頂點 添加進 ，更新 中頂點最短距離

第5步 ：選取頂點 添加進 ，更新 中頂點最短距離

第6步 ：選取頂點 添加進 ，更新 中頂點最短距離

第7步 ：選取頂點 添加進 ，更新 中頂點最短距離

示例：node編號1-7分別代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))輸出結果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))輸出結果：

示例：

找到D（4）到G（7）的最短路徑：

[1] 維基網路，最短路徑問題： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra演算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/

『叄』 直觀理解：單源點最短路徑——Dijkstra演算法

  Dijkstra演算法是由荷蘭計算機科學家 Edsger Wybe Dijkstra於1959年提出的單源點最短路徑演算法（SSSP:Single Souce Shortest Path）。是一個解決加權圖（不含負權重的邊）中從一個頂點到其餘各個頂點最短路徑問題的演算法。Dijkstra演算法是一個集 貪心演算法 ， 廣度優先搜索（BFS） 和 動態規劃 於一身的最短路徑演算法。Dijkstra演算法的主要特點是從起源點開始，採用貪心演算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接頂點，直到擴展到終點為止。
  Dijkstra演算法通過維護兩個集合： (已求出最短路徑的頂點)和 （未求出最短路徑的頂點），每次迭代地從 中移除路徑距離最小的點到集合 中，並通過這個新移入的點來更新 中各個頂點到源點的最短路徑，直到集合 為空。下面我們通過一個例子來簡單描述Dijkstra演算法的過程。
  假設我們有如下的圖，其中頂點A未此次演算法的起點：

  首先我們需要初始化兩個集合 和 ，以及 中每個頂點到源點的距離，若不直接於A相鄰，結果置為正無窮∞。

   Step 1： 從集合 中挑選出距離最小的點，這里會挑選出頂點F，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 2:： 從集合 中挑選出距離最小的點，這里會挑選出頂點E，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 3： 從集合 中挑選出距離最小的點，這里會挑選出頂點C，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 4： 從集合 中挑選出距離最小的點，這里會挑選出頂點D，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 5： 從集合 中挑選出距離最小的點，這里會挑選出頂點B，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 6： 從集合 中挑選出距離最小的點，這里會挑選出頂點G，集合 和 變更為： ， ，由於集合 為空，演算法停止迭代，輸出結果。

  以上就是對Dijkstra演算法的計算過程的簡單描述。

『肆』 數學建模第四章 圖論 part4.2最短路徑問題-Dijkstra演算法

1.Dijkstra演算法介紹

演算法特點：

迪科斯徹演算法使用了廣度優先搜索解決賦權有向圖或者無向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。

演算法的思路

Dijkstra演算法採用的是一種貪心的策略，聲明一個數組dis來保存源點到各個頂點的最短距離和一個保存已經找到了最短路徑的頂點的集合：T，初始時，原點 s 的路徑權重被賦為 0 （dis[s] = 0）。若對於頂點 s 存在能直接到達的邊（s,m），則把dis[m]設為w（s, m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大。初始時，集合T只有頂點s。 

然後，從dis數組選擇最小值，則該值就是源點s到該值對應的頂點的最短路徑，並且把該點加入到T中，OK，此時完成一個頂點， 

然後，我們需要看看新加入的頂點是否可以到達其他頂點並且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那麼就替換這些頂點在dis中的值。 

然後，又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。

2、Dijkstra演算法示例演示

我求下圖，從頂點v1到其他各個頂點的最短路徑.

首先第一步，我們先聲明一個dis數組，該數組初始化的值為：

我們的頂點集T的初始化為：T={v1}

既然是求 v1頂點到其餘各個頂點的最短路程，那就先找一個離 1 號頂點最近的頂點。通過數組 dis 可知當前離v1頂點最近是 v3頂點。當選擇了 2 號頂點後，dis[2]（下標從0開始）的值就已經從「估計值」變為了「確定值」，即 v1頂點到 v3頂點的最短路程就是當前 dis[2]值。將V3加入到T中。 

為什麼呢？因為目前離 v1頂點最近的是 v3頂點，並且這個圖所有的邊都是正數，那麼肯定不可能通過第三個頂點中轉，使得 v1頂點到 v3頂點的路程進一步縮短了。因為 v1頂點到其它頂點的路程肯定沒有 v1到 v3頂點短.

OK，既然確定了一個頂點的最短路徑，下面我們就要根據這個新入的頂點V3會有出度，發現以v3 為弧尾的有： < v3,v4 >,那麼我們看看路徑：v1–v3–v4的長度是否比v1–v4短，其實這個已經是很明顯的了，因為dis[3]代表的就是v1–v4的長度為無窮大，而v1–v3–v4的長度為：10+50=60，所以更新dis[3]的值,得到如下結果： 

因此 dis[3]要更新為 60。這個過程有個專業術語叫做「鬆弛」。即 v1頂點到 v4頂點的路程即 dis[3]，通過 < v3,v4> 這條邊鬆弛成功。這便是 Dijkstra 演算法的主要思想：通過「邊」來鬆弛v1頂點到其餘各個頂點的路程。

然後，我們又從除dis[2]和dis[0]外的其他值中尋找最小值，發現dis[4]的值最小，通過之前是解釋的原理，可以知道v1到v5的最短距離就是dis[4]的值，然後，我們把v5加入到集合T中，然後，考慮v5的出度是否會影響我們的數組dis的值，v5有兩條出度：< v5,v4>和 < v5,v6>,然後我們發現：v1–v5–v4的長度為：50，而dis[3]的值為60，所以我們要更新dis[3]的值.另外，v1-v5-v6的長度為：90，而dis[5]為100，所以我們需要更新dis[5]的值。更新後的dis數組如下圖： 

然後，我們使用同樣原理，分別確定了v6和v2的最短路徑，最後dis的數組的值如下： 

因此，從圖中，我們可以發現v1-v2的值為：∞，代表沒有路徑從v1到達v2。所以我們得到的最後的結果為：