最佳路径选择中双向Dijkstra算法的应用

作者：吴昊; 刘素红; 陈路遥; 于崇超

来源：公路交通科技(应用技术版), 2008, (02): 142-144.

• 城市交通
• Dijkstra算法
• 双向Dijkstra算法

最佳路径选择有利于解决城市交通拥堵。文章在传统Dijkstra算法的基础上,利用双向Dijkstra算法进行最佳路径选择,将算法时间复杂度由O(n2)减少到O(n*(n-1)/2),提高了算法效率。同时根据城市交通网络实时变化的特点,引入时间权值进行网络约束,使网络权值更加全面地反映路段信息。该算法已应用于北京市城市交通路网最短路径选择系统中,应用实例证明了该算法是可行的和准确的。

• 单位
  遥感科学国家重点实验室; 北京师范大学