基于启发式策略的最短路径算法

作者：陈曦; 费奇; 李炜

来源：华中科技大学学报(自然科学版)科技大学, 2006, (12): 4-6.

DOI：10.13245/j.hust.2006.12.002

• Dijkstra算法
• 最短路径
• 启发式策略
• 动态方向限制搜索算法

在讨论经典Dijkstra算法和启发式策略算法(A*,矩形算法等)的基础上,提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径.该算法结合人类的搜索思路和动态灵活的处理方式,对最短路径算法的搜索策略进行改进,动态改变搜索限制区域,减少计算时间.该算法不仅可以单独提高计算最短路径的效率,而且与其他算法结合起来还可取得更好的效果.实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50%的搜索节点数和搜索时间.

• 单位
  华中科技大学