Negative-weight single-source shortest paths in near-linear time

[Submitted on 7 Mar 2022 (v1), last revised 30 Oct 2022 (this version, v4)]

Download PDF

Abstract: We present a randomized algorithm that computes single-source shortest paths
(SSSP) in $O(mlog^8(n)log W)$ time when edge weights are integral and can be
negative. This essentially resolves the classic negative-weight SSSP problem.
The previous bounds are $tilde O((m+n^{1.5})log W)$ [BLNPSSSW FOCS’20] and
$m^{4/3+o(1)}log W$ [AMV FOCS’20]. Near-linear time algorithms were known
previously only for the special case of planar directed graphs [Fakcharoenphol
and Rao FOCS’01].


In contrast to all recent developments that rely on sophisticated continuous
optimization methods and dynamic algorithms, our algorithm is simple: it
requires only a simple graph decomposition and elementary combinatorial tools.
In fact, ours is the first combinatorial algorithm for negative-weight SSSP to
break through the classic $tilde O(msqrt{n}log W)$ bound from over three
decades ago [Gabow and Tarjan SICOMP’89].