The Shortest Path Parallel Algorithm on Single Source Weighted Multi-level Graph

Aiming at the single source shortest path problem on the single source weighted multi-level graph, this paper brings forward a new and practical parallel algorithm on 2-D mesh network by constructing a model of vector-matrix multiple and choosing the planar evenly partition method. The parallel algorithm is propitious to handle different sizes of multi-level graph structure by the use of its simple and regular characteristic, and our algorithm only needs less computation resources. The parallel algorithm was implemented on MPI. The theoretical analysis and the experimental results prove that the parallel algorithm has the good performances in terms of speed-up ratio and parallel efficiency, and its performance is a little better than the parallel dijkstra algorithm.