Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Bo Mao, Xinkai Shu, Longhui Yin · arXiv (Cornell University) · 2025
A Rust/Python shortest-paths library containing a production Dijkstra and a semantically faithful, bit-exact-verified implementation of the Duan–Mao–Mao–Shu–Yin O(m log^(2/3) n) "sorting barrier" algorithm (arXiv:2504.17033). The research record documents an algorithm-level variant study and two low-level optimization passes that bring the engineered BMSSP variant to ~1.1–1.2x of Dijkstra's wall-clock time at n = 10^6–10^7, ahead of published implementations, together with the honest negative result: no practical input size at which BMSSP overtakes Dijkstra was found, and a combinatorial duplicate cascade triggered by the paper's relax-on-equality rule on tie-rich graphs is documented and fixed.