Abstract: In view of the serial search for the shortest path algorithm inherent limitations and the difficult to raising the issue of search speed as the size of the network increases，the parallel shortest path search algorithm is designed and implemented based on the parallel Dijkstra’s algorithm idea.The complexity of the algorithm reduces to O（N²/p+N*（p-1）） as compared with the complexity O（N²） of serial Dijkstra’s algorithm.Experimental results show that the parallel shortest path search algorithm has fast and stable performance.The algorithm has better performance when the network contains a substantial number of nodes.

Key words: the shortest path, parallel computer environment, Message Passing Interface（MPI）, parallel search algorithm

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

关键词: 最短路径, 并行机环境, Message Passing Interface（MPI）, 并行搜索算法