Calculating Apsp Of Large Graphs With Limited Resources

All pairs shortest path(APSP)is a typical problem of graph computing,and it is closely related to the solution method of average path length,which is the most basic feature for describing complex systems.What’s more,with the increasing of the need in production activies,effiency play a more and more significant role,research focus on shortest paths are increasingly becoming the basis of research in different professions,providing effective solutions for problems such as transportation and travel route selection.For the above reasons,the all pairs shortest path problem is of great theoretical importance and high practicality.Despite the emergence of optimization algorithms for solving shortest paths,the difficulty of solving APSP has increased as the size of graphs has expanded dramatically.For large-scale graph data,the computational resources of a single machine cannot carry the task of computing the APSP at once,so several distributed graph computing systems have been investigated to achieve distributed computing for large-scale graph data.However,distributed clusters again imply higher cost and are often unavailable to the average user.In summary,it is of great importance to find a method for solving the APSP of large-scale graphs in a single-computer.In this paper,we propose a partitioning strategy for solving the APSP of large-scale graphs,which divides a large graph into several smaller subgraphs.Next calculates the APSP of each subgraph separately and merges the paths of the subgraphs to obtain the APSP of the whole graph.In this process,an efficient graph partitioning algorithm is applied to obtain an optimal sequence of vertices,and the vertices in the graph are partitioned sequentially according to the order of the vertices in the sequence,ultimately allowing a large-scale graph to be partitioned with fewer partition points and at a faster speed.Then,a modified Dijkstra algorithm is used on each subgraph to find the respective APSP,and then the paths are stitched together by using the same partition points between the subgraphs to compute the APSP result for the whole graph.In addition,this paper also draws on the idea of LRU strategy to permute the grid in memory.The algorithm proposed in this paper works well on real graph datasets and provides an effective method for solving the average shortest path and central mesogeneity of larger sized graphs with limited resources,which provides support for studying the topology of networks and solving practical problems.