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

关键词：最短路径 并行算法 加速比 

单位：上海交通大学安泰经济与管理学院; 上海200052; 吉林大学交通学院; 长春130022; 青岛大学自动化工程学院; 青岛266071