交通网络最短路径标号算法的实现与效率分析

被引:8
作者
陈洁
陆锋
机构
[1] 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室
关键词
最短路径算法; 标号算法; 复杂度; 交通网络;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种D ijkstra算法为核心的标号设定算法是各种商用G IS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法———基于逼近桶结构和改进四叉堆的D ijkstra算法(D IKBA与D IKQH)以及Pallottino算法(TWO-Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力。
引用
收藏
页码:1134 / 1138
页数:5
相关论文
共 7 条
[1]   GIS领域最短路径搜索问题的一种高效实现 [J].
王开义 ;
赵春江 ;
胥桂仙 ;
宋晓宇 .
中国图象图形学报, 2003, (08) :105-110
[2]   最短路径算法:分类体系与研究进展 [J].
陆锋 .
测绘学报, 2001, (03) :269-275
[3]   基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法 [J].
陆锋 ;
卢冬梅 ;
崔伟宏 .
中国图象图形学报, 1999, (12) :32-38
[4]   Dijkstra最短路径算法的一种高效率实现 [J].
乐阳 ;
龚健雅 .
武汉测绘科技大学学报, 1999, (03) :209-212
[5]  
网络优化[M]. 清华大学出版社 , 谢金星,邢文训编著, 2000
[6]  
Shortest paths algorithms: Theory and experimental evaluation[J] . Boris V. Cherkassky,Andrew V. Goldberg,Tomasz Radzik.Mathematical Programming . 1996 (2)
[7]  
Shortest path algorithms[J] . Giorgio Gallo,Stefano Pallottino.Annals of Operations Research . 1988 (1)