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

[摘要]路径规划问题是应急资源配送中的核心问题，最短路径算法在路径规划过程中起着决定性的作用，在众多路径规划算法中最经典且最具代表性的就是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算法的改进算法。……