Shortcutting for Negative-Weight Shortest Paths
George Z. Li, Jason Li, Satish Rao, Junkai Zhang
2026Year
3Citations
Abstract
Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in O(n 2.5 log 4.5 n) time, improving on prior work of Fineman (STOC 2024) and Huang-Jin-Quanrud (SODA 2025, 2026) on dense graphs. Our main technique is an shortcutting procedure that iteratively reduces the number of negative-weight edges along shortest paths by a constant factor.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 5a251596-4ff8-43ae-983a-dc66cb38cdf8Builds on6
- Negative-Weight Single-Source Shortest Paths in Near-linear TimeAaron Bernstein, Danupon Nanongkai, Christian Wulff-NilsenFOCS 2022 · 24 citations
- Breaking the Sorting Barrier for Directed Single-Source Shortest PathsRan Duan, Jiayi Mao, Xiao Mao, Xinkai Shu et al.STOC 2025 · 8 citations
- A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted GraphsRan Duan, Jiayi Mao, Xinkai Shu, Longhui YinFOCS 2023 · 6 citations
- Faster single-source shortest paths with negative real weights via proper hop distanceYufan Huang, Peter Jin, Kent QuanrudSODA 2025 · 5 citations
- Single-Source Shortest Paths with Negative Real Weights in Õ(mn8/9) TimeJeremy T. FinemanSTOC 2024 · 3 citations
Related papers
- From Hop Reduction to Sparsification for Negative Length Shortest PathsKent Quanrud, Navid TajkhorshidSTOC 2026 · 1 citation
- Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!Karl Bringmann, Alejandro Cassis, Nick FischerFOCS 2023 · 7 citations
- Faster negative length shortest paths by bootstrapping hop reducersYufan Huang, Peter Jin, Kent QuanrudSODA 2026 · 2 citations
- Incremental Single Source Shortest Paths in Sparse DigraphsShiri Chechik, Tianyi ZhangSODA 2021 · 5 citations
- Deterministic Padded Decompositions and Negative-Weight Shortest PathsJason LiSTOC 2026 · 6 citations
