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

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