并行最短路径搜索算法的设计与实现

作     者：卢照 师军 LU Zhao;SHI Jun

作者机构：陕西师范大学计算机科学学院西安710062 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2010年第46卷第3期

页      码：69-71页

摘      要：针对串行最短路径搜索算法本身固有的局限性,难以随着网络规模的增大而提高搜索速度的问题,设计并实现了一种基于并行Dijkstra思想的并行最短路径搜索算法,使算法复杂度由O(N2)减少到O(N2/p+N*(p-1)),提高了算法的效率。实验结果表明,该算法搜索速度快且性能稳定,当结点数目相当庞大时,算法的优越性更加明显。

主 题 词：最短路径 并行机环境 Message Passing Interface(MPI) 并行搜索算法 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3778/j.issn.1002-8331.2010.03.021

馆 藏 号：203240972...