| 一种实用的所有点对之间最短路径并行算法 |
| |
| 引用本文： | 周益民,孙世新,田玲. 一种实用的所有点对之间最短路径并行算法[J]. 计算机应用, 2005, 25(12): 2921-2922 |
| |
| 作者姓名： | 周益民 孙世新 田玲 |
| |
| 作者单位： | 电子科技大学,计算机科学与工程学院,四川,成都,610054;电子科技大学,计算机科学与工程学院,四川,成都,610054;电子科技大学,计算机科学与工程学院,四川,成都,610054 |
| |
| 摘 要： | 针对有向图中每对顶点之间的最短路径问题，在基于扩充了路径矩阵的串行Floyd算法上，提出了二维网格结构上的并行算法。选用的任务划分方法为二维均匀块分配方法。该并行算法已经在NOW上的MPI平台上实现，理论分析和数值实验表明它具有较高的扩展性和并行效率。
|
| 关 键 词： | 所有点对之间最短路径 Floyd算法 并行算法 |
| 文章编号： | 1001-9081（2005）12-2921-02 |
| 收稿时间： | 2005-09-02 |
| 修稿时间： | 2005-09-02 |
Practical parallel algorithm for all-pairs shortest-path problem |
| |
| ZHOU Yi-ming,SUN Shi-xin,TIAN Ling. Practical parallel algorithm for all-pairs shortest-path problem[J]. Journal of Computer Applications, 2005, 25(12): 2921-2922 |
| |
| Authors: | ZHOU Yi-ming SUN Shi-xin TIAN Ling |
| |
| Affiliation: | College of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu Sichuan 610054,China |
| |
| Abstract: | 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. |
| |
| Keywords: | all-pairs shortest-path problem Floyd algorithm parallel algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
