Abstract: The single-source shortest path problem is an important graph primitive.It computes the shortest paths in a weighted graph from a source vertex to every other vertex.Combining the classical Dijkstra's algorithm and Bellman-Ford's algorithm,Δ-stepping algorithm is used widely to complete SSSP computations in parallel settings.Due to the generic mechanism of preferential attachment,most large-scale networks are significantly skewed in the vertex degree distributions.This paper presents two strategies that utilize the skewness to improve the efficiency and scalability of Δ-stepping algorithm on large graphs.A preprocessing is executed on the input graph to compute an upper bound for the distance between every pair of vertices.The preprocessing results are used to reduce the redundant edge relaxations in Δ-stepping algorithm,so to improve the algorithm's efficiency and scalability in parallels settings.First,these upper bounds are used to reduce the relaxed edges.An edge is skippable in the SSSP computation when its weight is greater than upper bound of the distance between the connected vertices.Second,they are used to reduce relaxations repeated on the same edges.During the computation,a vertex is forbidden to be relaxed before its tentative distance to the source vertex has been updated to be less than the upper bound.Experimental results show that the improved algorithm on the Graph500 benchmark graphs provides nearly 10 ×performance improvement over its implementation on Graph500,and the performance improvement is between 2.68 and 5.58 on some real graphs.

Key words: Large-scale graph, Performance optimization, Shortest path, Δ-stepping algorithm