好久不见，我又回来了，这段时间把路径规划的一系列算法整理一下，感兴趣的点个关注。今天介绍一下机器人路径规划算法中最基础的 Dijkstra 算法，文末有 python 完整代码，那我们开始吧。

1959 年，荷兰计算机科学家 ·EdsgerWybe·Dijkstra 发表了论文《 A note on two problems in connexion with graphs 》，提出了 Dijkstra 算法。发展至今日，Dijkstra 算法成为了解决带权图最短路径问题的经典算法之一，现在常常被用于网络内部路由问题的求解或者作为其它的复杂图论算法的子算法辅助进行计算。?

近年来，Dijkstra 算法在许多领域得到广泛应用，比如：物流中心分层选址[1]、电网故障行波定位[2]、电能路由策略[3]。众多学者作了研究，比如：徐洋洋等人提出将Dijkstra 算法应用于交通阻塞路径规划中，生成的最佳路径有效避开拥堵路段[4]；吴红波等人提出 Dijkstra 算法和 GIS 网络分析的有效集成不但可以实现城市车辆行驶路线优化决策，而且 Dijkstra 算法优化能减少节点访问次数和时间复杂度[5]；王芝麟等人提出使用最小二叉堆作为 Dijkstra 最短路径算法的辅助数据结构，有效降低算法的运算次数并提高运算效率[6]。

参考文献：

[1] 靳国伟,何世伟,黎浩东,何必胜,殷玮川.Harmony Search-Dijkstra 混合算法在铁路物流中心分层选址中的应用[J].北京交通大学学报,2016,40(04):45-52.

[2] 李泽文,唐平,曾祥君,肖仁平,赵廷.基于 Dijkstra 算法的电网故障行波定位方法[J].电力系统自动化,2018,42(18):162-168.

[3] 江渝,叶泓炜,张青松,王克,徐志鹏,杨睿.能源互联网中基于 Dijkstra 算法的分布式电能路由策略的实现[J].电网技术,2017,41(07).

[4] 吴红波,王英杰,杨肖肖.基于 Dijkstra 算法优化的城市交通路径分析[J].北京交通大学学报,2019,43(04):116-121+130.

[5] 王芝麟,乔新辉,马旭,严研.一种基于二叉堆的Dijkstra 最短路径优化方法[J].工程数学学报,2021,38(05):709-720.

Dijkstra 算法是典型的单源最短路径计算算法，用于解决源点到其它所有点之间的最短路径计算的问题。它采用了贪心的思想搜索全局，求取最优解，搜索过程是以起点为圆心，向周围以同心圆的方式进行无序扩张搜索，搜索完全部节点后算法才终止。经典 Dijkstra 算法的搜索过程如下图所示，最外层的实线圆代表所有待搜索的点的集合。?

而下图展示了 Dijkstra 算法的一般运算流程，为了更直观的描述运算过程，下面以图论的方法来描述 Dijkstra 算法：设 G=(V,E) 是一个带权有向图。其中 V 表示图中所有顶点的集合，E 表示图中每条边的长度权值。

将顶点集合 V 分为两组，第一组为已找到最短路径的顶点集合，用 Close 表示，初始 Close 集合中只包含有源节点，每求得一条最短路径, ?就将对应的中间结点加入到集合 Close 中；

第二组为其余未确定最短路径的顶点集合，用 OPEN 表示。按最短路径的递增次序依次把第二组中的顶点加入 Close 中。

此外，每个顶点都对应着一个距离，Close 中的顶点的距离就是从 v 到此顶点的最短路径长度，OPEN 中的顶点的距离是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前路径的最短长度。其中节点到自身的距离视为 0。

算法步骤如下：

Step1：初始时，生成集合 Close={v}，集合 OPEN={其余顶点}，集合 Close 和 OPEN 互补；

Step2：从集合 OPEN 中选取一个距离 v 最小的顶点 k，把 k 加入集合 Close 中（该距离就是 v 到 k 的最短路径），记录节点 v 为节点 k 的父节点；

Step3：以 k 为新考虑的中间点，修改 OPEN 集合中各顶点的距离：若从源点 v 到顶点 u 的距离比原来距离短，则修改顶点 u 的距离值，修改后的距离值为顶点 k 的距离加上边上的权，同时修改节点 k 的父节点；

Step4：重复 Step2 和 Step3 直到所有顶点都包含在集合 Close 中；

Step5：根据目标节点的父节点反向进行迭代，输出最短路径。?

接下来将以下图所示的井下巷道的局部点网图为例，使用 Dijkstra 算法进行最优路径规划并列表进行算法的运算步骤说明，图中距离单位均为千米。

A 点为矿井副井口，即逃生终点，H 点为井下被困人员的当前位置，即逃生起点，搜索过程从 H 点开始，逐渐向外开始搜索，一直到搜索完所有节点才停止。

初始时，Close 表中仅包含起点 H，OPEN 表中包含有其余所有的节点。从 F 点开始进行搜索。下表中列出了基于 Dijkstra 算法的最短疏散路径求解过程。?

从求解过程中可以看到，不管需要求取最短路径的是哪两个点，Dijkstra 算法总会求出从源节点到图 G 中所有顶点的最短路径。反映到算法的计算过程，就是将集合 S 从仅含有源节点的一个集合逐步变成为全集，U 集合变为空集。求取完成之后，再根据父节点进行推演得出所需求解的最短路径。?

算法优点：鉴于 Dijkstra 算法的全局遍历性，其计算结果准确性非常高，Dijkstra 算法可以避开局部最优陷阱，100%的求解出最优路径。

算法缺点：但是正由于其要求遍历所有节点，在路径节点比较多的时候，计算速度会大大降低。由于 Dijkstra 算法使用了两次循环，所以它的时间复杂度为?，其中 n 为图中的顶点个数。在顶点数较多的情况下，算法的运算效率将受到影响，

算法的一般求解流程用伪代码表示如下：?

实现效果图如下，左图为搜索过程，右图为最终路径

?老样子每句都有注释，有问题可以在评论区留言