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

作　　者：吴昊[1] 刘素红[1] 陈路遥[2] 于崇超[1] 

机构地区：[1]北京师范大学地理学与遥感科学学院遥感科学国家重点实验室,北京100875 [2]北京师范大学资源学院资源技术与工程研究所北京师范大学环境演变与自然灾害教育部重点实验室,北京1000875

出　　处：《公路交通科技（应用技术版）》2008年第2期142-144,共3页

基　　金：长江学者和创新团队发展计划资助(PCSIRT);国家“十五”科技攻关课题(2003BA808A16-6)

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

关 键 词：城市交通 DIJKSTRA算法 双向Dijkstra算法 

分 类 号：U116.2[交通运输工程]