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

Understand

We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O(m\log^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].