# Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths

Preprint · Xiaojun Dong, Yan Gu, Yihan Sun, Yunming Zhang

- Archive id: arxiv:2105.06145
- Published: 2021-05-13
- DOI: https://doi.org/10.1145/3409964.3461782
- arXiv: https://arxiv.org/abs/2105.06145
- Source URL: https://arxiv.org/abs/2105.06145
- PDF: https://arxiv.org/pdf/2105.06145
- Provenance: arxiv

## Abstract

In this paper, we study the single-source shortest-path (SSSP) problem with positive edge weights, which is a notoriously hard problem in the parallel context. In practice, the $Δ$-stepping algorithm proposed by Meyer and Sanders has been widely adopted. However, $Δ$-stepping has no known worst-case bounds for general graphs. The performance of $Δ$-stepping also highly relies on the parameter $Δ$. There have also been lots of algorithms with theoretical bounds, such as Radius-stepping, but they either have no implementations available or are much slower than $Δ$-stepping in practice. We propose a stepping algorithm framework that generalizes existing algorithms such as $Δ$-stepping and Radius-stepping. The framework allows for similar analysis and implementations of all stepping algorithms. We also propose a new ADT, lazy-batched priority queue (LaB-PQ), that abstracts the semantics of the priority queue needed by the stepping algorithms. We provide two data structures for LaB-PQ, focusing on theoretical and practical efficiency, respectively. Based on the new framework and LaB-PQ, we show two new stepping algorithms, $ρ$-stepping and $Δ^\*$-stepping, that are simple, with non-trivial worst-case bounds, and fast in practice. The stepping algorithm framework also provides almost identical implementations for three algorithms: Bellman-Ford, $Δ^\*$-stepping, and $ρ$-stepping. We compare our code with four state-of-the-art implementations. On five social and web graphs, $ρ$-stepping is 1.3--2.5x faster than all the existing implementations. On two road graphs, our $Δ^\*$-stepping is at least 14\\% faster than existing implementations, while $ρ$-stepping is also competitive. The almost identical implementations for stepping algorithms also allow for in-depth analyses and comparisons among the stepping algorithms in practice.

_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.