An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917279593136128 |
|---|---|
| author | Khanna, Sanjeev Song, Junkai |
| author_facet | Khanna, Sanjeev Song, Junkai |
| contents | We present a randomized algorithm for the single-source shortest paths (SSSP) problem on directed graphs with arbitrary real-valued edge weights that runs in $n^{2+o(1)}$ time with high probability. This result yields the first almost linear-time algorithm for the problem on dense graphs ($m = Θ(n^2)$) and improves upon the best previously known bounds for moderately dense graphs ($m = ω(n^{1.306})$).
Our approach builds on the hop-reduction via shortcutting framework introduced by Li, Li, Rao, and Zhang (2025), which iteratively augments the graph with shortcut edges to reduce the negative hop count of shortest paths. The central computational bottleneck in prior work is the cost of explicitly constructing these shortcuts in dense regions. We overcome this by introducing a new compression technique using auxiliary Steiner vertices. Specifically, we construct these vertices to represent large neighborhoods compactly in a structured manner, allowing us to efficiently generate and propagate shortcuts while strictly controlling the growth of vertex degrees and graph size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16638 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths Khanna, Sanjeev Song, Junkai Data Structures and Algorithms We present a randomized algorithm for the single-source shortest paths (SSSP) problem on directed graphs with arbitrary real-valued edge weights that runs in $n^{2+o(1)}$ time with high probability. This result yields the first almost linear-time algorithm for the problem on dense graphs ($m = Θ(n^2)$) and improves upon the best previously known bounds for moderately dense graphs ($m = ω(n^{1.306})$). Our approach builds on the hop-reduction via shortcutting framework introduced by Li, Li, Rao, and Zhang (2025), which iteratively augments the graph with shortcut edges to reduce the negative hop count of shortest paths. The central computational bottleneck in prior work is the cost of explicitly constructing these shortcuts in dense regions. We overcome this by introducing a new compression technique using auxiliary Steiner vertices. Specifically, we construct these vertices to represent large neighborhoods compactly in a structured manner, allowing us to efficiently generate and propagate shortcuts while strictly controlling the growth of vertex degrees and graph size. |
| title | An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.16638 |