最短路徑問題是圖論研究中壹個經典算法問題，旨在尋找圖中兩節點或單個節點到其他節點之間的最短路徑。根據問題的不同，算法的具體形式包括：
常用的最短路徑算法包括：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] 維基百科，最短路徑問題： /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/