GIS系列專題（4）：使用貪心算法（Dijkstra Algorithm）解決最短路徑問題（Calculating shortest path in QGIS）

1、最短路徑問題介紹

問題解釋：

從圖中的某個頂點出發到達另外一個頂點的所經過的邊的權重和最小的一條路徑，稱為最短路徑。

解決問題的算法：

最鄰近距離法

遺傳算法

2、Dijkstra算法介紹（即貪心算法）

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

迪傑斯特拉算法是目前已知的解決單源最短路徑問題的最快算法，Time complexity: O(n^2)

單源（single source）最短路徑，就是從一個源點出發，考察它到任意頂點所經過的邊的權重之和為最小的路徑.

GIS系列專題（4）：使用貪心算法（Dijkstra Algorithm）解決最短路徑問題（Calculating shortest path in QGIS）

迪傑斯特拉算法不能處理權值為負數或為零的邊，因為本質上它是一種貪心算法，出現了負數意味着它可能會舍棄一條正确的邊，而選擇一個長邊和一個負數邊，因為長邊和負數邊的權值之和可能小于那條正确的邊.

算法的思路：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中包含了圖的所有頂點。

知乎的回答：

https://www.zhihu.com/question/20630094

C++開源實作：

https://github.com/Nerdylicious/DijkstraShortestPath https://github.com/Superone77/AGV_dijkstra https://github.com/thinkphp/dijkstra https://github.com/seung-lab/dijkstra3d https://github.com/ibaaj/dijkstra-cartography

3、QGIS最短路徑分析

QGIS使用的是dijkstra算法。源碼：

https://github.com/qgis/QGIS/blob/master/src/analysis/network/qgsgraphanalyzer.cpp https://github.com/qgis/QGIS/blob/master/src/analysis/network/qgsgraphanalyzer.h

4、DXF2GCODE最短路徑

DXF2GCODE使用的是最鄰近距離法，不是貪心算法。

https://sourceforge.net/projects/dxf2gcode/

x、自動駕駛路徑規劃技術

經典搜尋算法，動态規劃