基于预处理的点到点最短路径计算方法

An algorithm for point to point shortest paths based on preprocessing

基于经典的Dijkstra算法,研究采用预处理的点到点最短路径算法。通过引入双向Dijkstra和基于reach的预处理方法形成新的RE算法,并利用C++编程设计算法程序,将新算法应用于交通工程领域。利用EFSS数据结构搭建考虑交叉口和路段延误的交通网络,检验新算法的适用性和效率,结果发现RE算法与Dijkstra算法相比,搜索速度有大幅提升且能保证路径查询的正确性,RE算法在大规模网络上优势更为显著,查询时间约为Dijkstra算法的10%。

Based on the classical Dijkstra algorithm,an algorithm for point to point shortest paths based on preprocessing was studied.The bidirectional Dijkstra algorithm and the reach-based preprocessing method were introduced to establish the new RE algorithm in this paper.The program of the new algorithm was compiled with C＋＋ and the new algorithm was applied to traffic engineering field.Traffic networks considering delay on roads and intersections were constructed by using EFSS data structure to test the applicability and efficiency of RE algorithm.The results reveal that compared with the original Dijkstra algorithm,the RE algorithm has a significant increase in the search speed and can ensure the correctness of path query.On large-scale networks,the new RE algorithm shows great advantages and its query time is approximately 10% of the Dijkstra algorithm.