Breakthrough Tracker record
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
The authors gave a deterministic O(m log^(2/3) n)-time algorithm for directed single-source shortest paths in the comparison-addition model. It is the first to beat Dijkstra's O(m + n log n) bound on sparse directed graphs in that model.
← Back to the filtered Breakthrough Tracker
- Stable ID
directed-sssp-sorting-barrier-2025- Revision
directed-sssp-sorting-barrier-2025.v1- Field
- Computer Science · Graph algorithms and data structures
- Evidence
- Tier 1 · Peer reviewed: Yes
- Record state
- Current · Verified/accepted conference result
- Last checked
AI role
No AI assistance was disclosed in the paper or linked reporting.
Record details
- Problem or result
- Single-source shortest paths in directed graphs with non-negative real edge weights
- Authors
- Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu and Longhui Yin
- Institutions
- Tsinghua University, Stanford University and Max Planck Institute for Informatics
- Result date
- April 23, 2025; published at STOC 2025
Why it matters
The result shows that the sorting-like overhead in Dijkstra's method is not an unavoidable barrier for this foundational graph problem.
Limits
The improvement is asymptotic and model-specific to non-negative real weights in the comparison-addition model. It does not establish faster performance on current routing workloads or small-integer-weight graphs.
Sources
- Primary: Open proceedings record
- Primary: Primary preprint on arXiv
- Independent: Quanta Magazine explanation
Correction and revision history
- Initial entry.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.