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

作者：高松; 陆锋; 段滢滢

来源：武汉大学学报(信息科学版), 2008, (04): 418-421.

DOI：10.13203/j.whugis2008.04.001

• K则最优路径算法
• 双向搜索
• Dijkstra算法 Kth shortest path algorithm
• bidirectional search
• Dijkstra's algorithm

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

• 单位
  中国科学院研究生院; 资源与环境信息系统国家重点实验室