As the title suggests, I’m curious whether anyone has successfully implemented the single-source shortest path (SSSP) algorithm introduced in this recent paper.
It would be exciting to see someone put this breakthrough to the test on a real competitive-programming benchmark, specifically the classic CSES “Shortest Routes I” problem.
To make things more fun, I’m offering $100 (not a lot, but just for motivation) to the first person who can demonstrate a correct solution using this new algorithm that ranks within the top five fastest submissions on the CSES leaderboard.
If you’ve experimented with the paper’s approach or have an implementation that can compete with the best, please share your results!
The new SSSP has a much higher constant factor than Dijkstra's, so it will be basically impossible to make it outperform constant-optimized Dijkstra on graphs as small as $$$n=10^5$$$
The new SSSP would be better for n>=1e7 graphs, the cses has n capped at 1e5. Also with larger constant factors it would probably be worst if not better for cses route 1 specifically.
This paper shows a benchmark between the new SSSP algorithm and Dijkstra.