A Practical Parallel Algorithm for All-Pair Shortest Path Based on Pipelining
Hua Wang, Ling Tian, Chunhua Jiang · 2008
On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path (APSP) problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.