摘要
针对有向图中每对顶点之间的最短路径问题,在基于扩充了路径矩阵的串行Floyd算法上,提出了二维网格结构上的并行算法。选用的任务划分方法为二维均匀块分配方法。该并行算法已经在NOW上的MPI平台上实现,理论分析和数值实验表明它具有较高的扩展性和并行效率。
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.
出处
《计算机应用》
CSCD
北大核心
2005年第12期2921-2922,2934,共3页
journal of Computer Applications
