基于并行计算的大规模图多源最短路径算法设计  

All-pair Shortest Path Algorithm Based on Parallel Computing

作　　者：万一红 徐常福 

机构地区：[1]江西财经大学软件与通信工程学院,江西南昌330032

出　　处：《科技广场》2017年第4期68-72,共5页Science Mosaic

摘　　要：大数据时代的到来,社交网络、交通网络等抽象的图结构的规模也越来越大,面对数据量大、结构复杂的图数据的最短路径计算,原始的最短路径算法已经不再适用,数据的并行化处理是大规模图计算较为常用的方法。在实际应用中往往需要计算任意两点间的最短路径,因此多源最短路径算法的研究是有意义的。本文参考Floyd算法思想,提出一个并行处理的大规模图多源最短路径算法,该算法将图中节点与边的关系抽象为矩阵,再通过矩阵分割的方式,将超大规模的矩阵切分为多个子矩阵进行并行处理,减少最短路径计算中算法迭代时间复杂度以提高算法的执行效率。In the era of big data, graph structures such as social network and transportation network are becoming increasingly large. At present, graph data are in great amount and original shortest path algorithms are no longer appropriate. Parallel processing is a common method for large-scale graph calculation. In actual application, we need to compute the shortest path between any two points, and, therefore, the study of multi-source shortest path algorithm makes sense. In this paper, referring to the main idea of Floyd algorithm, we present a parallel multi-source shortest path algorithm for large-scale graph. This calculation abstracts the relationship between nodes and edges in the graph as a matrix, divides the large matrix into several sub-matrices and processes them in parallel. It can reduce the iteration time complexity, improving the efficiency of the algorithm.

关 键 词：多源最短路径 并行计算 矩阵分割 

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