Practical parallel algorithm for all-pairs shortest-path problem
一种实用的所有点对之间最短路径并行算法

Aiming at the all-pairs shortest-path problem in the directed graph, a practical parallel algorithm, which based on the Floyd algorithm with an extended path array, was brought forward on 2-13 mesh network . The planar evenly partition method was chosen for task division in this parallel algorithm. The parallel algorithm was implemented on MPI on NOW. The theoretical analysis and the experimental results prove that the parallel algorithm is an efficient and scalable algorithm.