# Parallel Shortest-Paths Using Radius Stepping

Preprint · Guy E. Blelloch, Yan Gu, Yihan Sun, Kanat Tangwongsan

- Archive id: arxiv:1602.03881
- Published: 2016-02-11
- arXiv: https://arxiv.org/abs/1602.03881
- Source URL: https://arxiv.org/abs/1602.03881
- PDF: https://arxiv.org/pdf/1602.03881
- Provenance: arxiv

## Abstract

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 $Δ$-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 $Δ$. Each step settles the vertices in its annulus but can take $Θ(n)$ substeps, each requiring $Θ(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 $Δ$-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(\\frac{n}ρ \\log ρL)$, for a total of $O(\\frac{kn}ρ \\log ρL)$ substeps, each parallel. We describe how to preprocess a graph to have this property. Altogether, Radius-Stepping takes $O((m+n\\log n)\\log \\frac{n}ρ)$ work and $O(\\frac{n}ρ\\log n \\log (ρL))$ depth per source after preprocessing. The preprocessing step can be done in $O(m\\log n + nρ^2)$ work and $O(ρ^2)$ depth or in $O(m\\log n + nρ^2\\log n)$ work and $O(ρ\\log ρ)$ depth, and adds no more than $O(nρ)$ edges.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.