基于改进Dijkstra的应急指挥车及时救援的最短路径算法的研究

王先全 周锡祥 余浩源 李浩 王向雨

摘要：随着人们自驾出游的频率逐步提高，城市交通拥挤堵塞的情况时常出现，给应急指挥车的救援带来诸多不便，为使应急指挥车能够机动灵活地深入城市各个角落，及时有效解决各类突发事故，通过ArcMap以城市交通道路为源构建了网络数据集，将城市交通道路网抽象为图的结构，使用邻接表以及二叉排序树结构对传统Dijkstra算法进行了改进，并基于改进后的Dijkstra算法，采用ArcGIS Engine、Visual Studio等工具开发了应急指挥车最短路径规划软件，实现了应急指挥车最短路径的规划。

关键词：城市交通;应急指挥车;邻接表;二叉排序树;Dijkstra

中图分类号：U412      文献标识码：A

文章编号：1009-3044（2021）14-0001-03

Abstract： As people gradually increase the frequency， drive travel city traffic jam often appear， to bring inconvenience， emergency command vehicle rescue emergency command vehicle can be flexible in order to make into all corners of the city， the timely and effective to solve all kinds of accidents， by ArcMap for urban traffic source network data set is constructed， the urban traffic road network abstraction for figure structure， using adjacency list and binary sort tree structure of the traditional Dijkstra algorithm is optimized， and the Dijkstra algorithm based on the optimized， The shortest path planning software of emergency command vehicle is developed by using ArcGIS Engine， Visual Studio and other tools， and the shortest path planning of emergency command vehicle is realized.

Key words： the urban traffic; emergency command vehicle; adjacency list; binary sort tree; Dijkstra

1 背景

为了处理自然灾害、火灾、安全生产等各种事故，政府相关部门必须装备应急指挥车[1]。应急指挥车是处置各突发事件的现场机动指挥中心，能够机动灵活地深入城市各个角落，及时有效地解决各类突发事件[2]。应急指挥车在第一时间到达事发地点，需要规划出一条最短路径。最短路径不仅指距离最短，还通常引申到费用、时间等度量，相应地，最短路径问题便转变为最低费用问题、最短时间问题[3]。本文研究的是最短时间问题。影响时间的因素很多，需要综合考虑距离、道路交叉点数、路况、交通拥挤程度等因素，为应急指挥车规划出一条耗时最少的路径。本文优化了Dijkstra算法，采用ArcGIS Engine、Visual Studio等工具开发应急指挥车最短路径规划软件，实现了基于Dijkstra算法优化的应急指挥车的最短路径的规划。

2 建立网络模型

城市交通主要由众多的街道相连、相交而构成，并且组成错综复杂、纵横交错的城市交通道路网[4]。本文通过ArcGIS的网络数据集工具在道路的每个交叉口处进行打断处理，整个交通道路网便由交叉路口以及路段构成，将交通网中道路的交叉点抽象为图中的结点，路段抽象为图中的弧段[5]，以此建立如图1所示的城市交通道路网络模型。

式中：[ RN]表示城市交通道路网络;N表示网络中的结点集合;R表示网络中的路段集合，其元素为有序对[（x，y）]，[（x，y）]表示结点[x]与结点[y]之间存在一条有向通路，[ lxy]表示结点[x]与结点[y]之间的路段的加权长度[7]。路段的加权长度是综合考虑多个因素后求解所得到的长度，包括路径长度，路况、交通拥挤程度等因素。

3 传統Dijkstra算法

3.1 Dijkstra算法描述

Dijkstra算法是在1959年由荷兰计算机科学家E.W.Dijkstra提出的图论中求最短路径的常用算法[8]。它适用于单源的最短路径规划问题，即求出图中一点到其余任一顶点的最短路径[9]。它的主要思想为：将图中所有结点分为两组，第一组为已求出到起始点的最短路径的结点集合，用Y表示，初始时Y中仅有起始点一个元素，之后每求得一条某顶点到起始点的最短路径，就将该顶点加入Y集合，直到目标点或者图中所有结点加入Y中，算法便结束了;第二组为其余未确定最短路径的结点集合，用S表示，按照最短路径长度的递增次序依次把S中的结点加入Y集合，在加入的过程中，总保持从起始点到Y集合各结点的最短路径长度不大于从起始点到S集合任何结点的最短路径长度[10]。

3.2 Dijkstra算法实现步骤

算法中需要用到四个辅助数组来存放数据，第一个为布尔类型的Status[]数组，同来保存结点的当前状态，若为TURE，则表示该结点已经加入Y集合中，若为FALSE，则表示该结点还属于S集合，第二个为浮点类型的Dis[]数组，用来存放图中各个结点到起始点的加权长度，第三个为整数类型的Path[]数组，用来存储最短路径上该结点前一个结点的序号，以上三个数组的大小均等于结点的数量，第四个数组是一个浮点类型的二维数组，命名为Matrix，作用与邻接矩阵相同，用来保存各个结点到其余结点的加权长度，若两结点之间不存在有向通路，则存入数组的值为无穷大∞，表示两结点不相连，该二维数组的行数和列数均为结点的数量。图2所示为Dijkstra算法的实现过程。

1）初始化四个辅助数组，循环给数组赋初始值，将城市交通道路网中的道路的加权长度装入Matrix数组。

2）得到起点的序号j，令Status[j]=TRUE，将起点的状态由未标记状态修改为已标记状态。

3）通过循环查询Dis[]数组，找到S集合中距离Y集合结点加权长度最短的结点k。

4）将结点k加入Y集合。

5）更新结点k状态修改后各数组的值。

6）重复步骤3）-5），直到将目标结点或者图中所有结点加入Y集合，才结束算法。

7）通过循环查找Path[]数组，便能够获得该最短路径经过的所有结点的序号，如此便成功规划出最短路径。

为方便理解，以圖3所示的路径结点网络为例，规划结点A到结点E的最短路径，其步骤为：

1）将起始点A加入Y集合，计算Y集合到T集合中各点（B、C、D、E）的距离，将值储存到Dis[]数组和Path[]数组中，如表1所示，并通过Dis[]数组找到最邻近点B。

2）将结点B加入Y集合，重新计算距离，更新Dis[]数组和Path[]数组的值，如表2所示，并从S集合中找到最邻近点D。

3）将结点D加入Y集合，得到如表3所示的Dis[]数组和Path[]数组的值，查找Dis[]数组，找到最邻近点C。

4）将C加入Y集合，再次更新Dis[]数组和Path[]数组的值，如表4所示，找到最邻近点E。

5）将目标点E加入Y集合，通过循环查找Path[]数组，便能得到从A到E的最短路径：A→B→D→C→E。

传统的Dijkstra算法虽然能成功实现最短路径的规划，但不论是时间复杂度，还是空间复杂度，都是o（N2）（N表示结点数量），随着结点数量的增加，占用的计算机存储空间和算法运行时间都成指数形势的增长，故需要在传统的Dijkstra基础上进行优化。

4 Dijkstra算法优化

4.1 存储方式优化

表示图最简单的方法就是使用二维数组，称为邻接矩阵表示法，对于任意两个结点[x]，[y]，若[x]与[y]之间存在通路，则置Matrix[x][y]的值为路段[（x，y）]的加权长度，若[x]与[y]之间不存在通路，则置Matrix[x][y]的值为无穷大∞。虽然采用邻接矩阵的表示方法易于编程且容易实现，但是该方法的空间复杂度为o（N2），空间需求会随着结点数量的增多而成指数形势的增长，且会浪费大量的空间来存储不相邻结点的无用加权长度∞。比邻接矩阵更好的存储方式是邻接表，邻接表是一个二维容器，第一维存储结点序号，第二维存储该结点所对应的路段集，如果路段有加权值，附加的信息同样也可以保存到邻接表中。如对应前文图3所示的路径结点网络，若分别用邻接矩阵和邻接表的方式来存储，得到的结果如图4和图5所示。

用邻接表的方式来存储，空间复杂度为o（N+e），空间需求相对于道路网的结点数量来说是线性增加的。相比于邻接矩阵的空间复杂度o（N2），采用邻接表的方式很大程度减少了所占用的计算机存储空间。

4.2 基于二叉排序树的优化

采用邻接表的方式减少的是空间复杂度，Dijkstra算法的时间复杂度仍为o（N2），每次查找下一个符合要求的结点都需要对所有的中间结点进行一次遍历，额外计算量较大，针对该问题，引入了数据结构中的二叉排序树结构，提前对中间结点进行一次从小到大的排序操作。图6表示的是典型的二叉排序树，引入二叉排序树后的Dijkstra算法的实现流程如图7所示。

1）初始化数组，将起点加入Y集合。

2）求取Y集合的最后一个元素的邻接结点，将邻接结点的加权长度加入二叉排序树中进行排序操作。

3）根据二叉排序树的定义，最小权值将出现在树的最左侧，选取加权长度值最小的点L，将其加入Y集合。

4）判断L是否为目标点，如果是，算法搜索结束，如果不是，则重复步骤2）-3），直到搜索到目标点为止。

使用二叉排序树优化后的算法在查找下一个符合要求的结点时所消耗的时间大大减少，其时间复杂度为o（nlogn）。

5 实例分析

本文采用ArcGIS Engine、Visual Studio等工具开发了应急指挥车路径规划软件。选取重庆市的道路网络作为研究数据，将省道、铁道、市区主干道等矢量要素添加到地理数据库中，通过ArcGIS的网络数据集工具得到了前文图1所示的重庆交通道路网络图，并将优化后的Dijkstra算法嵌入到软件中，规划出了应急指挥车的最短路径，如图8所示。

在繁杂交叉路口、事故现场、医院、商圈等位置节点车流量大，交通拥挤，规划路径时需添加障碍点，有效避开交通拥挤的位置节点，得到如图9所示的最短路径。

在车辆行驶速度理想的状态下，假定经过一个交叉路口平均等待30s，图8的最短路径长为4619.8m，经过13个交叉路口，所用时间为13.4min，图9的路线长为4718.5m，经过11个交叉路口，消耗12.6min。图9的路线有效地避开了交通拥挤路段，虽然相比图8行驶了更长的距离，但是却消耗了更少的时间。

6 结束语

本文使用邻接表以及二叉排序树对Dijkstra算法进行了优化，节省了计算机的存储空间，减少了算法的执行时间，提高了算法的运行效率，并将优化后的算法应用于应急指挥车路径规划软件中，实现了应急指挥车最短路径的规划。在城市交通中，不仅仅要考虑到起始点与目标点之间的路段长度，还要考虑路段的路况、路障、交通的拥挤程度等因素，只有综合考虑更多的交通因素，使构建的城市交通模型更接近实际生活中的城市交通网络，得到的最短路径才能更准确，更符合实际需求。

参考文献：

[1] 梁晓辉，慕永辉，吴北华，等.关于路径规划的相关算法综述[J].价值工程，2020，39（3）：295-299.

[2] Tamatjita E N，Mahastama A W.Shortest path with dynamic weight implementation using Dijkstra's algorithm[J].ComTech：Computer，Mathematics and Engineering Applications，2016，7（3）：161.

[3] 赵青，朱乐天.基于ArcGIS的最短路径算法在城市交通中的应用[J].航空计算技术，2014，44（2）：14-17.

[4] Abhishek Goyal，Prateek Mogha，Rishabh Luthra，et al.Path finding：A* or Dijkstra's[J].International Journal in IT & Engineering，2014，2（1）：1-15.

[5] 黄杭.浅谈Dijkstra算法与Floyd算法[J].中国新通信，2019，21（3）：162-163.

[6]逄淑玲，王晓升.Dijkstra算法的并行实现[J].微型机与应用，2017，36（9）：25-27.

[7] 吴红波，王英杰，杨肖肖.基于Dijkstra算法优化的城市交通路径分析[J].北京交通大学学报，2019，43（4）：116-121，130.

[8] 王特起，谢亚琴.基于Dijkstra算法的校园导航系统的设计与实现[J].通信技术，2019，52（8）：1937-1943.

[9] 张本俊，周海娇，刘淑琴.改进Dijkstra算法在公共交通出行的研究[J].物联网技术，2018，8（11）：45-48.

[10] 王旭，刘毅，李国燕.基于改进Dijkstra算法的移动机器人路径规划[J].天津城建大学学报，2018，24（5）：378-381，386.

【通联编辑：谢媛媛】