改进Dijkstra算法的城市道路最短路径仿真研究

Improved Dijkstra algorithm for shortest path in urban traffic net

本文在分析Dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的Dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度。仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15%～25%,当节点越多这种减少越明显,可提高搜索路径的实时性。

The paper proposed a bidirectional search improved Dijkstra algorithm based on the characteristic of the urban road network and Dijkstra algorithm. Result showed that the improved Dijkstra algorithm could reduce the searching range by 15% ~ 25% , the more the nodes are, the more obvious the reduction. The improved algorithm could improve the real-time in path searching.