arXiv:2504.17033cs.DS
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.
Linked by 8 identifiable commenters in 8 comments across 6 threads, from Jun 2025 to Feb 2026. Found in 12 HN submissions from May 2025 to Aug 2025. Open submission discussions.
> 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)…
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
Here is the paper https://arxiv.org/abs/2504.17033
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…
Original paper: https://arxiv.org/abs/2504.17033
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…
https://arxiv.org/abs/2504.17033
https://arxiv.org/abs/2504.17033
Connected through shared HN threads, not inferred similarity or a recommendation.
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…
danalecView on HNParent context