Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin
2025Year
8Citations
8Top-tier citations
Abstract
We give a deterministic O(m log 2/3 n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m + n log n) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.
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 211fe55e-e1bc-48fa-afb8-8fc09f2f2f9bCited by top-tier papers8
- Universal Optimality of Dijkstra Via Beyond-Worst-Case HeapsBernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan et al.FOCS 2024 · 33 citations
- Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic TimeXiao Mao, Aviad RubinsteinSTOC 2026 · 4 citations
- Shortcutting for Negative-Weight Shortest PathsGeorge Z. Li, Jason Li, Satish Rao, Junkai ZhangSTOC 2026 · 3 citations
- Faster negative length shortest paths by bootstrapping hop reducersYufan Huang, Peter Jin, Kent QuanrudSODA 2026 · 2 citations
- Trust Region Interior Point Methods: Optimal ℓ₂- and Faster Wide-Neighborhood Path FollowingDaniel Dadush, Haoyuan Ma, Bento Natura, László A. VéghSTOC 2026 · 1 citation
Builds on5
- Universal Optimality of Dijkstra Via Beyond-Worst-Case HeapsBernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan et al.FOCS 2024 · 33 citations
- Negative-Weight Single-Source Shortest Paths in Near-linear TimeAaron Bernstein, Danupon Nanongkai, Christian Wulff-NilsenFOCS 2022 · 24 citations
- Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!Karl Bringmann, Alejandro Cassis, Nick FischerFOCS 2023 · 7 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
Related papers
- Single-Source Shortest Paths with Negative Real Weights in Õ(mn8/9) TimeJeremy T. FinemanSTOC 2024 · 3 citations
- Deterministic Padded Decompositions and Negative-Weight Shortest PathsJason LiSTOC 2026 · 6 citations
- Parallel Exact Shortest Paths in Almost Linear Work and Square Root DepthNairen Cao, Jeremy T. FinemanSODA 2023 · 4 citations
- Incremental Single Source Shortest Paths in Sparse DigraphsShiri Chechik, Tianyi ZhangSODA 2021 · 5 citations
- Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSPAdam Karczmarz, Wojciech Nadara, Marek SokolowskiSODA 2026
