两种策略下的最短路径并行算法研究与实现

• 作者: 倪安宁 李杰 贾洪飞 隽志才
• 来源期刊: 系统工程理论方法应用
• 学科: 工学
• 关键词: 最短路径 并行算法 加速比
• 年，卷（期）: 2006,（2）
• 所属期刊栏目: 学术论文
• 页码范围: 123-127
• 页数: 5页
• 分类号: TP391
• 字数: 3929字
• 语种: 中文
• DOI: 10.3969/j.issn.1005-2542.2006.02.006

摘要

随着智能交通运输系统的研究与应用,对在大规模交通网络上求解最短路径的实时性提出了更高的要求.为了找出适用于实际交通网络的高效最短路径并行算法,首先选取了3种最短路径标号串行算法,以此为基础分别实现了网络复制及网络分割两种策略下求解最短路径的并行算法.最后,从基于GIS的交通规划软件TransCAD中提取了实际交通路网数据,同时还随机产生了不同规模的稀疏格网,在这些网络中对并行算法的性能进行了测试和分析.结果表明,在8台机器上求解含5181个节点的实际交通网络中32个源点的最短路径时,基于网络分割的双队列标号修正并行算法的加速比可达到6.32,在其他网络中也表现出较好的加速比及可扩展性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李杰	青岛大学自动化工程学院	43	230	9.0	13.0
2	贾洪飞	吉林大学交通学院	74	1757	24.0	40.0
3	隽志才	上海交通大学安泰经济与管理学院	109	1945	22.0	39.0
4	倪安宁	吉林大学交通学院	5	113	5.0	5.0