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

Preprint · Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen

- Archive id: arxiv:2203.03456
- Published: 2022-03-07
- arXiv: https://arxiv.org/abs/2203.03456
- Source URL: https://arxiv.org/abs/2203.03456
- PDF: https://arxiv.org/pdf/2203.03456
- Provenance: arxiv

## Abstract

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\].

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.