Help Privacy Policy Disclaimer
  Advanced SearchBrowse





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


Nanongkai,  Danupon       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 591KB

Supplementary Material (public)
There is no public supplementary material available

Bernstein, A., Nanongkai, D., & Wulff-Nilsen, C. (2023). Negative-Weight Single-Source Shortest Paths in Near-linear Time. Retrieved from https://arxiv.org/abs/2203.03456.

Cite as: https://hdl.handle.net/21.11116/0000-000E-6D7F-B
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].
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(m\sqrt{n}\log W)$ bound from over three
decades ago [Gabow and Tarjan SICOMP'89].