最短路徑演算法dijkstra

❶ 圖遍歷演算法之最短路徑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/