> “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
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.
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•2h ago
larodi•41m ago
kzrdude•39m ago
bob1029•35m ago
https://en.wikipedia.org/wiki/Splay_tree