Breaking the sorting barrier for directed single-source shortest paths
12 comments
·August 6, 2025polytely
> But curiously, none of the pieces use fancy mathematics.
> “This thing might as well have been discovered 50 years ago, but it wasn’t,” Thorup said. “That makes it that much more impressive.”
this is so cool to me, it feel like a solution you could* have stumbled upon while doing game development or something
*probably wouldn't but still
aDyslecticCrow
I'm intrigued but the article is very verbose with little detail. Mabie the paper will give a more satisfying description.
Im most curiosity how the algorithm fulfil the "global minima" that djixtra guarantees. The clumping of front-tier nodes seem prone to missing some solutions if unlucky.
ljlolel
Tarjan was my algorithms professor. He invented many of them
flafla2
O(m log^2/3 n) !!! What a triumph.
supernetworks_
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.
ape4
Sounds a lot more complicated that Dijkstra. But I guess that's the way it goes.
larodi
Dijkstra is still very difficult for many and not universally taught in 7th grade even though you can arguably explain what a shortest path in a graph is to 14 y.o.
GolDDranks
Dijkstra _could_ be universally taught in 7th grade if we had the curriculum for that. Maybe I'm biased, but it doesn't seem conceptually significantly more difficult than solving first degree equations, and we teach those in 7th grade, at least in Finland where I'm from.
cantor_S_drug
reminds me of TimSort.
https://arxiv.org/abs/2504.17033