摘要
针对传统的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.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第12期135-137,共3页
Computer Engineering and Applications
基金
国家自然科学基金资助项目(编号:70371070/G0116)
上海市教委科研项目资助项目(编号:05EZ34)
上海市重点学科建设资助项目(编号:T0502)
