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

摘要：

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

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

所属期刊栏目：46

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2010-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：69-71