1、最短路径问题介绍
问题解释：
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径。
解决问题的算法：
最邻近距离法
遗传算法
2、Dijkstra算法介绍（即贪心算法）
算法特点：迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
迪杰斯特拉算法是目前已知的解决单源最短路径问题的最快算法，Time complexity: O(n^2)
单源（single source）最短路径，就是从一个源点出发，考察它到任意顶点所经过的边的权重之和为最小的路径.
迪杰斯特拉算法不能处理权值为负数或为零的边，因为本质上它是一种贪心算法，出现了负数意味着它可能会舍弃一条正确的边，而选择一个长边和一个负数边，因为长边和负数边的权值之和可能小于那条正确的边.
算法的思路：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、自动驾驶路径规划技术
经典搜索算法，动态规划
https://zhuanlan.zhihu.com/p/128518988
高速公路路径规划
https://zhuanlan.zhihu.com/p/128516264
---
https://qgis.org/zh-Hans/site/
https://blog.csdn.net/wsh6759/article/details/6994448
https://gis-lab.info/qa/road-graph-eng.html
https://blog.csdn.net/wsh6759/category_932711.html
