高松, 陆锋, 段滢滢. 一种基于双向搜索的K则最优路径算法[J]. 武汉大学学报 ( 信息科学版), 2008, 33(4): 418-421.
引用本文: 高松, 陆锋, 段滢滢. 一种基于双向搜索的K则最优路径算法[J]. 武汉大学学报 ( 信息科学版), 2008, 33(4): 418-421.
GAO Song, LU Feng, DUAN Yingying. A Kth Shortest Path Algorithm Implemented with Bi-directional Search[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 418-421.
Citation: GAO Song, LU Feng, DUAN Yingying. A Kth Shortest Path Algorithm Implemented with Bi-directional Search[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 418-421.

一种基于双向搜索的K则最优路径算法

A Kth Shortest Path Algorithm Implemented with Bi-directional Search

  • 摘要: 提出了一种基于双向搜索策略的K则最优路径算法,以改进的Dijkstra最优路径算法为基础,从起点和终点同时搜索,分别构造正序和逆序最优路径树,计算网络中两点之间的多条参考K则最优路径。详细描述了算法设计思想和运行过程,分析了算法的时间复杂度,并通过实际路网验证了算法的效率和精度。

     

    Abstract: A new Kth shortest path algorithm based on bidirectional search is set forward in this paper.Based on the classical Dijkstra's shortest path algorithm,the presented algorithm conducts the path searching both from the source and destination nodes at the same time,and constructs the shortest path trees in positive and reverse sequence alternately so to populate several reasonable shortest paths between the start and destination nodes.The principle and implementation of the algorithm is described in detail and time complexity is analyzed.The efficiency and accuracy are verified with a real road network.

     

/

返回文章
返回