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

• 作者: 陆锋 陈洁
• 来源期刊: 中国图象图形学报
• 学科: 地球科学
• 关键词: 最短路径算法 标号算法 复杂度 交通网络
• 年，卷（期）: 2005,（9）
• 所属期刊栏目: 学术论文与技术报告
• 页码范围: 1134-1138
• 页数: 5页
• 分类号: TP302.7|P208
• 字数: 5406字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-8961.2005.09.011

摘要

标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种Dijkstra算法为核心的标号设定算法是各种商用GIS平台网络分析算法的首选.然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用.为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法--基于逼近桶结构和改进四叉堆的ijkstra算法(DIKBA与DIKQH)以及Pallottino算法(TWO_Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陆锋	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	91	3249	28.0	56.0
2	陈洁	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	90	1445	18.0	36.0