A Practical Parallel Algorithm for All-Pair Shortest Path Based on Pipelining |
| |
| Authors: | Hua Wang Ling Tian Chun-Hua Jiang |
| |
| Affiliation: | School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, 610054, China |
| |
| Abstract: | 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. |
| |
| Keywords: | All-pair shortest path Floydalgorithm pipelining parallel algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
