Negative-Weight Single-Source Shortest Paths in Near-linear Time

We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O\left(m \log ^{8}(n) \log W\right)$ time when edge weights are integral and can be negative.1This essentially resolves the classic negative-weight SSSP problem. The previous bounds are $\tilde{O}\left(\left(m+n^{1.5}\right) \log W\right)$ [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 $O(m \sqrt{n} \log W)$ bound from over three decades ago [Gabow and Tarjan SICOMP’89].