基于MPI的中国教育网最短路并行算法  

Parallel Algorithm(MPI) on Solving the Shortest-path Problem of China Educational Network

作　　者：倪小军[1] 张宁[1] 王美娟[1] 

机构地区：[1]上海理工大学管理学院系统工程研究所,上海200093

出　　处：《计算机工程与应用》2006年第12期135-137,共3页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(编号:70371070/G0116);上海市教委科研项目资助项目(编号:05EZ34);上海市重点学科建设资助项目(编号:T0502)

摘　　要：针对传统的Floyd算法难以解决中国教育网的平均最短路径长度计算问题,在对网络进行度分析的基础上,设计了一种宽度优先搜索(BFS)并行算法,该算法可有效地避免对出度为0的节点进行搜索,采用VC编写基于MPI(MessagePassingInterface)的并行程序,通过20台电脑连网计算分析,该方法取得了令人满意的结果。Due to large space demand and long time consumption,the traditional Floyd algorithm is not suitable for solving the shortest-path problem among any pair of vertices of china educational network,which includes about 366 422 vertices and 540 755 edges.By analyzing the degree distribution characteristic ,a Breadth-First Search（BFS） parallel algorithm is proposed,which can effectively avoid searching those＂zero-out-degree＂vertices.Finally,after executing the parallel program on a local network which contains 20 micro-computers,the problem is satisfactorily resolved after about 2 hours computation.

关 键 词：复杂网络 最短路 BFS算法 MPI 并行计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]