最短路徑問題演算法
Ⅰ 最短路徑演算法
最短路徑的演算法主要有三種：floyd演算法、Dijkstra演算法、Bellman-Ford(貝爾曼-福特)
一、floyd演算法
基本思想如下：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點X到B。所以，我們假設Dis(AB)為節點A到節點B的最短路徑的距離，對於每一個節點X，我們檢查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設置Dis(AB) = Dis(AX) + Dis(XB)，這樣一來，當我們遍歷完所有節點X，Dis(AB)中記錄的便是A到B的最短路徑的距離。
三、Bellman-Ford(貝爾曼-福特)
演算法的流程如下：
給定圖G(V, E)（其中V、E分別為圖G的頂點集與邊集），源點s，
1.數組Distant[i]記錄從源點s到頂點i的路徑長度，初始化數組Distant[n]為, Distant[s]為0；
2.以下操作循環執行至多n-1次，n為頂點數：
對於每一條邊e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權值；
若上述操作沒有對Distant進行更新，說明最短路徑已經查找完畢，或者部分點不可達，跳出循環。否則執行下次循環；
3.為了檢測圖中是否存在負環路，即權值之和小於0的環路。對於每一條邊e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的邊，則圖中存在負環路，即是說該圖無法求出單源最短路徑。否則數組Distant[n]中記錄的就是源點s到各頂點的最短路徑長度。
可知，Bellman-Ford演算法尋找單源最短路徑的時間復雜度為O(V*E).
Ⅱ 圖文解析 | Dijkstra單源最短路徑演算法
給定 加權有向圖 G=(V,E,W)，每條邊的權值w為 非負數 ，表示兩個頂點間的距離。
源點s∈V。
求：從s出發到其他各個頂點的最短路徑。
如上圖所示，以1為源點，計算到其餘各個頂點的最短距離（我已用紅線標出）。下面列出了最終解：
S集合 ：當從s到x（x ∈V ）的最短路徑找到時，則x ∈S。當所有頂點都進入S集合時，演算法結束。
初始：S=｛s｝，當S=V時演算法結束。
從s到u相對於S的最短路徑 ：指從s到u且僅經過S中頂點的最短路徑。
dist[u]:從s到u相對於S的最短路徑長度
short[u]:從s到u最短路徑的長度（演算法最終解）
dist[u] ≥ short[u]
Dijkstra演算法採用貪心演算法模式，演算法過程就是通過計算dist[u],不斷擴充S集合，同時dist[u]會不斷優化改善，直到dist[u] = short[u]，並將其放到S中，當所有頂點都放入S集合時，演算法結束。
輸入：加權有向圖G=(V,E,W)
V={1,2,…,n}, s=1
輸出：從s到每個頂點的最短路徑
輸入：G=(V,E,W)，源點1
V={1,2,3,4,5,6}
初始S集合只有1，計算直接從1能到達的頂點的距離，其他不能從1號頂點直接到達的頂點都記為無窮大。雀輪睜此時從dist[u]里找出最短距離的頂點（6號），並將其放進S集合。
S={1}
dist[1] = 0
dist[2] = 10
dist[6 ] = 3
dist[3] = ∞
dist[4] = ∞
dist[5] = ∞
當把6號頂點放進S集合後，經由6號頂點出發到達的頂點的最短距離可能會被優化更新，因為該演算法的思想很「貪心」，誰更短我要誰！比如1->6->2要比1->2距離更短，所以dist[2]被更頃歲新為5，從專業術語上講，這個「更新」過程叫做鬆弛，其他點同理。然桐喚後從dist[u]里找出最短的路徑的那個頂點（5號），並放進S集合里。
S={1,6}
dist[1] = 0
dist[6] = 3
dist[2] = 5
dist[4] = 9
dist[5] = 4
dist[3] = ∞
後面的操作步驟其實就是重復上面的操作。即當S集合里有個新的頂點後，就可能會更新其他點的最短距離，更新一遍後，找出當前最短距離的dist[u]，並將該頂點放進S集合。後面不重復闡述。
S={1,6,5}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = ∞
S={1,6,5,2}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
S={1,6,5,2,4}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
S={1,6,5,2,4,3}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
當有向圖中的所有頂點都進入了S集合後，演算法結束，此時的dist[u]的值其實就是最初我們找出的那個最終解short[u]，所以，演算法結束時，dist[u]=short[u],得到最終解。
Ⅲ 最短路徑 - Dijkstra演算法
演算法每次都查找距離起始點最近的點，那麼剩下的點距離起始點的距離一定比當前點大。
1.選定A節點並初始化，如上述步驟3所示
2.執行上述 4、5兩步驟，找出U集合中路徑最短的節點D 加入S集合，並根據條件 if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 來更新U集合
3.這時候 A->B, A->C 都為3，沒關系。其實這時候他倆都是最短距離，如果從演算法邏輯來講的話，會先取到B點。而這個時候 if 條件變成了 if ( 'B 到 C,E 的距離' + 'AB 距離' < 'A 到 C,E 的距離' ) ，如圖所示這時候A->B距離 其實為 A->D->B
思路就是這樣，往後就是大同小異了
演算法結束
（圖片來源於網路）
Dijkstra演算法保證能找到一條從初始點到目標點的最短路徑，只要所有的邊都有一個非負的代價值。在上圖中，粉紅色的結點是初始結點，藍色的是目標點，而類菱形的有色區域則是Dijkstra演算法掃描過的區域。顏色最淡的區域是那些離初始點最遠的，因而形成探測過程（exploration）的邊境（frontier）。因而Dijkstra演算法可以找到一條最短的路徑，但是效率上並不高。
數據結構--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/