A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Path

We give the first parallel algorithm with optimal Õ(m) work for the classical problem of computing SingleSource Shortest Paths in general graphs with negative-weight edges.

In graphs without negative edges, Dijkstra’s algorithm solves the Single-Source Shortest Paths (SSSP) problem with optimal Õ(m) work, but is inherently sequential. A recent breakthrough by [Bernstein, Nanongkai, Wulff-Nilsen; FOCS ’22] achieves the same for general graphs. Parallel shortest path algorithms are more difficult and have been intensely studied for decades. Only very recently, multiple lines of research culminated in parallel algorithms with optimal work Õ (m) for various restricted settings, such as approximate or exact algorithms for directed or undirected graphs without negative edges. For general graphs, the best known algorithm by [Ashvinkumar, Bernstein, Cao, Grunau, Haeupler, Jiang, Nanongkai, Su; ESA ’24] still requires m1+o (1) work.

This paper presents a randomized parallel algorithm for SSSP in general graphs with near-linear work Õ (m) and state-of-the-art span n1/2+o(1). We follow a novel bottom-up approach leading to a particularly clean and simple algorithm. Our algorithm can be seen as a near-optimal parallel black-box reduction from SSSP in general graphs to graphs without negative edges. In contrast to prior works, the reduction in this paper is both parallel and essentially without overhead, only affecting work and span by polylogarithmic factors.