应急资源配送中Dijkstra改进算法的研究

石晓达　孙连英　葛娜　赵平　李子元

[摘要]路径规划问题是应急资源配送中的核心问题，最短路径算法在路径规划过程中起着决定性的作用，在众多路径规划算法中最经典且最具代表性的就是Dijkstra算法。以传统的Dijkstra算法分析为基础，从存储结构和算法过程两个方面进行一定程度的改进，目的是在节点数和边数较多的情况下，提高网络模型的处理效率。以真实道路交通数据为基础进行相关实验，结果证明，改进后的Dijkstra算法可以有效减少节点的计算量，提高算法的运行效率。

[关键词]Dijkstra算法；算法改进；路径规划

[中图分类号]TP 31156[文献标志码]A[文章编号]10050310（2018）0200

6106

Abstract： Path planning is the core issue in emergency resource distribution. The shortest path algorithm plays a decisive role in the path planning process. The most classic and most representative path planning algorithm is the Dijkstra algorithm. Based on the traditional Dijkstra algorithm analysis， a certain degree of improvement has been made in storage structure and the algorithm process. The purpose is to improve the efficiency of the network model with more nodes and more edges. Experiments are carried out on the basis of real road traffic data and the results show that the improved Dijkstra algorithm can effectively reduce the calculation of nodes and improve the efficiency of the algorithm.

Keywords： Dijkstra algorithm； Algorithm improvement； Path planning

0引言

Dijkstra算法是解决路径规划问题的核心算法。路径规划是指在行驶前或者行驶过程中向驾驶员提供参考行驶路线的过程，是车辆定位与导航系统的基本功能之一。路径规划过程中有着不同的优化标准，如最短距离、最少行驶时间及最大运载量[1]。但无论使用何种标准，路径规划最终都可以归类为在特定道路网络中以搜索总代价最小为目的的目标路径问题，所以最短路径问题正是网络分析中最关键、最重要的问题[2]。

随着信息技术的发展，最短路径问题在交通、地理、物流、道路规划及网络布局等实际生活中日益凸显出其重要性[3]。在解决最短路径问题的算法中，比较流行且具代表性的算法就是Dijkstra算法及其改进算法[4]。本文将针对传统的Dijkstra算法所面临的多节点数和多边数网络模型的应用局限性，主要討论Dijkstra算法的改进算法。

1经典的Dijkstra算法

11Dijkstra算法的基本思想

Dijkstra算法是典型的单源点最短路径算法，是由荷兰计算机科学家E.W.Dijkstra在1959年提出的[5]。Dijkstra算法的主要特点是以起始点为中心，向与之直接相连的点层层扩展，每次以距离最小化为判定标准，直到扩展到终点得到最短距离。

在抽象为图论的意义之下，用Dijkstra算法计算图中的最短路径时，需要指定起点s（即从顶点s开始计算）。另外需要加入两个集合S和U的运算，S集合用来记录已经求出最短路径的顶点以及起点与其他各顶点之间的暂时最短路径，U集合用来记录还未求出最短路径的顶点以及起点与其他各顶点之间的距离。

初始时，S中只有起点s；U中包括除起点s之外的所有顶点，且U中各顶点的路径是“起点s到该顶点的路径”。从U中遍历出路径最短的顶点，并将该顶点加到S中；更新U中各顶点对应的路径。然后循环上述过程，直到遍历完所有顶点，最终得到的路径长度即为起点s到所有顶点的最短路径长度。

12Dijkstra算法的操作步骤

1） 初始化：S集合中只含有起点s；U集合中含有除s之外的其他所有顶点，且各顶点距离标识为“起点s到该顶点的距离”，不直接相连标识为无穷大。即S{}=s，U{}=其他顶点，ds=0。源点标号为s，而其他点尚未处理。

2） 检验U中其他所有点到s的距离，并选出距离最小的一个点k，并将顶点k加入到集合S中，同时从集合U中删除顶点k。即：

dsk=min[dsj]。（1）

3） 更新集合U中起点s到所有其他各顶点的距离。更新原因是由于前一步已经确定了k是最短路径中的顶点，而前一顶点经过顶点k到达下一顶点的路径长度比直接到达下一顶点的路径长度小，这一可能性是存在的，那么就需要再次进行最短距离更新，以距离最小化为判定标准。即：

dsv =min[dsv，dsk+dkv]。（2）

4） 重复步骤2）和3），直到遍历完所有顶点，那么最终S集合包含所有顶点，U集合为空。S集合中的距离即为源点s到各顶点的最短距离。

13Dijkstra算法应用举例

下面用具体实例阐述Dijkstra算法在路径规划中的应用。如图1所示，点与连线是对实际交通道路网络拓扑部分结构的模拟，其中A至F各点代表各交通十字路口，点与点之间的连线代表各条道路。利用Dijkstra算法，求出点A到F的最短路径。

21最优存储结构的选取

对于网络数据的存储方式，有两种存储结构可以选取：邻接矩阵和邻接表。图论中对于网络数据的存储采用的是邻接矩阵的方法[7]。

将图以邻接矩阵的形式存储时，可以用二维数组表示任意两点之间的连接情况。当两点为同一节点时，对应的数组值为0，反之则不为0。当需要对两点之间的权值进行操作时，比如道路的长度、资源的数量等，如果两点是直接连接的，则对应的矩阵值就是两点之间的权值大小；如果两点不直接相连，则对应的矩阵值为无穷大。这种表示方法简单、直接。矩阵以数组的方式表示时申请和释放都比较灵活方便。但在网络节点数较多的情况下，需要大量的存储空间，尤其是在网络比较稀疏的情况下，邻接矩阵会存储较多无穷大的非计算网络节点，也会造成一定的空间浪费[8]。

将图以邻接表的形式存储时，存储空间大体相当于弧度表示法，灵活性比较强，并且存储空间较小。但在进行相应的节点操作时，程序的正确性不太容易把握，尤其在网络节点数量庞大时，操作性较差。

实验数据表明，在前期网络节点较少时，将同一种算法分别采用邻接表和邻接矩阵两种存储方式，其执行时间基本相同。随着网络节点数目的增多，邻接表不适用于

节点数量多的劣势明显突出，实验时间明显增加；而邻接矩阵并没有明显表现出其存储空间浪费从而影响算法执行效率的问题，实验时间缓慢稳定地增加。

在大规模交通疏散中，各应急避难点以网络节点的形式按照某种存储方式存储在网络中。在应急避难点较多的情况下，对比实验结果数据，采用邻接矩阵的存储方式进行网络节点的存储，效果较好。

22算法效率的改进策略

在Dijkstra算法的实现过程中可以看出，其中最主要的一个核心步骤就是从未选定为最短距离的网络节点中选择一个当前集合中权值最小的点，即距离源点最近的点[9]。这是一个循环比较的过程，如果中间不采取任何比较筛选策略，未标记的点将被逐一循环比较，在大数据量的网络节点的情况下，这无疑是制约计算速度的瓶颈。

221添加网络节点的标记flag

采用布尔值类型的数组flag对算法过程中的节点做标记。如果网络节点已经选定为最短距离节点，则标记为true，否则标记为false。初始化时，将所有网络节点的值都标记为false，算法过程中逐一选定修改，最终执行完所有（节点数减1次）循环后，所有节点都被选定完毕，其对应flag值都应当标记为true。对未选定的节点进行权值最小筛选时，只要筛选flag值为false的节点即可。

222添加最小路径变量min

采用整型变量min对未确定最短距离的网络节点的值作标记，通过比较选出最小距离。初始化定义整型变量min为最大值，伴随着数组的遍历，min的值会越来越小。在判别时，必须满足flag值为false并且min的值小于当前min，才会对该网络节点重新赋值并记录下当前节点的标记号，否则直接跳过。这种比较方法实现了每次搜索仅需一次循环便可找到未标记网络节点的最小权值。

23基于真实交通道路数据的相关实验

231实验数据

实验以北京市电子道路数据为基础数据，数据保存在shapfile格式的文件中。通过解析文件内容，读取道路相关数据，包括道路ID、形狀、宽度、方向、名称、起始节点ID、终止节点ID和长度等。电子道路数据总计87 855条，解析后按照ID依次排列于TXT文件中，解析结果如图2所示。北京市道路交通电子地图如图3所示。

232实验过程

以一条道路的起始节点作为整个实验道路数据节点中的起始节点，再以这条道路的终止节点作为后一条或几条道路的起始节点，通过层层扩展，建立真实道路的网络拓扑结构。

通过仅改变道路网络拓扑的复杂度的方法，即只改变道路节点数量，将选出的道路节点按照阿拉伯数字顺序依次编号，以当前道路节点到其他所有道路节点的最短距离为例，最后对Dijkstra算法运行时长进行比较，进行相关实验。

首先当道路网络拓扑图中节点数量为50和100的情况下，实验结果如图4所示。左侧是以邻接表形式存储数据的Dijkstra算法实验结果，节点数为50时算法运行时长为63 ms，节点数为100时算法运行时长为80 ms；右侧是以矩阵形式存储数据的Dijkstra算法实验结果，可以看出在节点数量为50和100的情况下，算法运行时长均与左侧结果相同。

逐渐增加道路网络拓扑中的节点数量，在节点数量为300、500和1 000时再次进行对比试验，实验结果如图5所示。左侧依然是以邻接表形式存储数据的Dijkstra算法实验结果，右侧是以矩阵形式存储数据的Dijkstra算法实验结果，可以发现在数据量逐渐增大的情况下，以邻接表形式存储数据明显不如矩阵形式使得算法的运行效率高。

3Dijkstra算法在路径规划中的应用

随着城市规模的不断扩大以及城市人口的高度密集，城市交通情况日益严峻，道路交通网络日益脆弱。尤其是伴随着很多交通事故和紧急事件的发生，大面积交通拥堵和交通瘫痪时常发生，因此应急资源配送以及最短路径寻优工作迫在眉睫[10]。

专门针对大规模事故灾害的应急资源储备点一般分布在整个城区，仿真数据如图6所示，以北京市交通电子道路地图为例，显示GIS系统中道路及应急资源储备点分布情况，其中应急资源储备点用红色元素标识。一旦城区某处或多处发生大规模灾害事故，在应急资源配送过程中，往往会面临从多个储备点向一个事故点的资源配送问题，如何才能找到距离最近的应急资源储备点显得格外重要。

Dijkstra算法在GIS系统中路径规划方面的应用很好地解决了这一问题。城市灾害事故发生时，

首先确立应急资源配送目的节点的坐标位置（X，Y），

然后通过目的节点坐标的确立，运用Dijkstra算法进行

路径规划，得到距离当前灾害事故发生点最近的一个或几个应急资源储备节点的坐标。如图7所示，确定距离灾害事故发生节点最近的3个应急资源储备节点。

4结束语

本文在传统Dijkstra算法的基础上，对该算法在存储结构和算法逻辑过程两个方面进行了改进。通过以网络节点数据量为自变量，算法的执行时间为因变量的相关编程实验，结果证明改进后的Dijkstra算法可以有效減少节点的计算量，执行效率相比之前有了明显的提高，在路径规划方面尤其是在应急资源配送的应用中有着很好的前景。基于Dijkstra算法的最短路径算法在物流管理、交通疏散等其他背景的应用中效果依然显著，这也是本文今后的研究方向。

[参考文献]

[1]苏永云，晏克非，黄翔，等.车辆导航系统的动态最优路径搜索方法研究[J].系统工程，2000， 18 （4）：32-37.

[2]乐阳， 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报， 1999， 24（3）： 209-212.

[3]彭定旭， 冀肖榆. Dijkstra算法的java实现方式及优化[J]. 黑龙江科技信息， 2017（4）： 166-167.

[4]龚杰辉，白玲，高健美. 最短路径算法的改进及其实现方法[J]. 解放军测绘学院学报， 1998，15（2）：121-124.

[5]段汝东， 侯至群， 朱大明. 基于Java的Dijkstra最短路径算法实现[J].价值工程， 2016， 35（21）： 208-210.

[6]李擎，宋顶立，张双江，等.两种改进的最优路径规划算法[J].北京科技大学学报， 2005， 27 （3）：367-370.

[7]孟庆伟， 张冬姣. 基于Dijkstra最短路径算法的优化及应用研究[J]. 电子商务， 2014（12）： 60-61.

[8]白洪涛， 孙吉贵， 焦洋，等. 网络优化算法的实现与比较[J]. 吉林大学学报（信息科学版）， 2002， 20（2）： 59-69.

[9]乐阳. 网络分析模型在GIS中的实现与应用[D]. 武汉：武汉测绘科技大学， 1999.

[10]张钰. 城市交通紧急疏散管理方法及应用研究[D]. 武汉：武汉理工大学， 2006.

（责任编辑白丽媛）