Parallel Shortest-Paths Using Radius Stepping

The single-source shortest path problem (SSSP) with nonnegative edge weights is a notoriously difficult problem to solve efficiently in parallel---it is one of the graph problems said to suffer from the transitive-closure bottleneck. In practice, the Delta-stepping algorithm of Meyer and Sanders (J. Algorithms, 2003) often works efficiently but has no known theoretical bounds on general graphs. The algorithm takes a sequence of steps, each increasing the radius by a user-specified value Delta. Each step settles the vertices in its annulus but can take Theta(n) substeps, each requiring Theta(m) work (n vertices and m edges). In this paper, we describe Radius-Stepping, an algorithm with the best-known tradeoff between work and depth bounds for SSSP with nearly-linear (otilde(m)) work. The algorithm is a Delta-stepping-like algorithm but uses a variable instead of fixed-size increase in radii, allowing us to prove a bound on the number of steps. In particular, by using what we define as a vertex k-radius, each step takes at most k+2 substeps. Furthermore, we define a (k, ρ)-graph property and show that if an undirected graph has this property, then the number of steps can be bounded by O(fracnρ log ρ L), for a total of O(fracknρ log ρ L) substeps, each parallel. We describe how to preprocess a graph to have this property. Altogether, Radius-Stepping takes O((m+nlog n)log fracnρ) work and O(fracnρlog n log (ρL)) depth per source after preprocessing. The preprocessing step can be done in O(mlog n + nρ2) work and O(ρ2) depth or in O(mlog n + nρ2log n) work and O(ρlog ρ) depth, and adds no more than O(nρ) edges.