复杂网络中最短路径算法的研究及应用

• 作者: 万润泽 罗飞 魏开平
• 来源期刊: 电子测量技术
• 学科: 工学
• 关键词: 最短路径算法 标号算法 复杂度 复杂网络
• 年，卷（期）: 2007,（4）
• 所属期刊栏目: 信息技术
• 页码范围: 169-171,197
• 页数: 4页
• 分类号: TP393
• 字数: 4080字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-7300.2007.04.050

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	万润泽	华中师范大学计算机科学系	7	30	4.0	5.0
2	罗飞	华中师范大学计算机科学系	4	18	3.0	4.0
6	魏开平	华中师范大学计算机科学系	10	73	5.0	8.0