After 38 Years, Five Researchers Break the Classic O(m + n log n) Bound for Sparse Shortest Paths
techNmak · x · 2026-09-03
For 38 years, no algorithm beat Dijkstra's O(m + n log n) bound for shortest paths on sparse directed graphs. In 2025, five researchers — Duan, Mao, Mao, Shu and Yin — finally did.
The key insight
- Dijkstra always picks the unfinished vertex with the smallest known distance, so vertices are processed in strictly increasing distance order.
- In the comparison-addition model, if output must be in distance order, Dijkstra is already optimal — the ordering itself is the bottleneck.
- But the shortest-path problem only asks for final distances, not sorted output. The new algorithm exploits exactly this gap.
How it works
Rather than always finding the single closest vertex next, the algorithm combines Dijkstra-style exploration, Bellman-Ford-style relaxations, and divide-and-conquer, processing vertices in batches to sidestep the ordering constraint and beat the long-standing bound on sparse directed graphs.
A landmark result in theoretical computer science with direct implications for the family of distance/ordering problems on graphs.
More from Research
- Google Officially Details Planetary Prediction Engine for Autonomous Global Modeling — TheTuringPost · 2026-09-03
- Google's Planetary Prediction Engine Shrinks Weeks-Long Geospatial Modeling to Minutes — TheTuringPost · 2026-09-03
- AI rebuilds the Iliad's Catalogue of Ships as an interactive 3D map with 1,186 vessels — eldonredwards · 2026-09-03
- Jan Kulveit: predicting few-body interactions is hard, million-part systems get easier again — gleech · 2026-09-03
- Hacking llama.cpp to hot-swap knowledge into Qwen's Ngram PLE table — ortegaalfredo · 2026-09-03
- Qwen Releases E-Commerce Bench: Agents Run Stores for 365 Days, Few Learn — Alibaba_Qwen · 2026-09-03