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

• 作者: 卢照 师军
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 最短路径 并行机环境 Message Passing Interface(MPI) 并行搜索算法
• 年，卷（期）: 2010,（3）
• 所属期刊栏目: 研发、设计、测试
• 页码范围: 69-71
• 页数: 3页
• 分类号: TP301.6
• 字数: 3281字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.03.021

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	师军	陕西师范大学计算机科学学院	42	566	11.0	23.0
2	卢照	陕西师范大学计算机科学学院	6	68	4.0	6.0