Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

I implemented the STOC 2025 Best Paper Award winner in C99. The algorithm achieves O(m log^(2/3) n) complexity, breaking the 65-year-old sorting barrier for sparse directed SSSP that Dijkstra established at O(m + n log n). *Key implementation details:* - Cache-optimized CSR layout for maximum spatial locality - Zero-allocation design with pre-allocated workspaces - Recursive subproblem decomposition instead of global priority queues *Benchmarks:* On graphs with 250k–1M nodes, this shows 20,000x+ speedups over standard Dijkstra implementations. The DMMSY core runs in ~800ns for 1M nodes. *Paper:* https://arxiv.org/pdf/2504.17033 *GitHub:* https://github.com/danalec/DMMSY-SSSP This is experimental—focused on correctness first. Would love feedback on edge cases, better decomposition strategies, or cache-oblivious optimizations I might have missed.

Should have a more conspicuous link to the Quanta article that it references if not the original. (It’s there, just not on the top.) https://www.quantamagazine.org/new-method-is-the-fastest-way... https://arxiv.org/abs/2504.17033

> What I'm missing is certainly what the hell the algorithm even is and what is its complexity. https://arxiv.org/pdf/2504.17033 - Linked from the second sentence of the submission, not hard to track down. And the complexity (by which I presume you mean algorithmic complexity) is stated in the submission and in the PDF linked by the submission and that I just shared with you.

In the article it does talk about how they arrived at a partial solution that only worked on undirected graphs, but then they started taking a hybrid approach to get it to work on directed graphs. The paper also indicates it works on directed graphs: https://arxiv.org/abs/2504.17033 That said, it might only be faster for large, sparse graphs.

https://arxiv.org/abs/2504.17033 We give a deterministic O(mlog2/3n)-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+nlogn) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.