DMMSY
A high-performance C99 implementation of the Single-Source Shortest Path (SSSP) algorithm introduced in:
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin,
"Breaking the Sorting Barrier for Directed Single-Source Shortest Paths", STOC 2025.
DMMSY provides a robust and efficient backend for solving SSSP problems on large-scale sparse graphs. By leveraging a recursive subproblem decomposition rather than a strict global priority queue, this implementation breaks the long-standing $O(m + n \log n)$ complexity barrier, delivering speedups exceeding 20,000x over standard Dijkstra implementations.
Key Features
Breaking the Sorting Barrier : Reduces the complexity factor to $O(\log^{2/3} n)$ , significantly outperforming $O(\log n)$ at scale.
: Reduces the complexity factor to , significantly outperforming at scale. Zero-Allocation Design : Careful manual memory management with pre-allocated workspaces to eliminate runtime overhead.
: Careful manual memory management with pre-allocated workspaces to eliminate runtime overhead. Cache-Optimized CSR Layout : High-density Compressed Sparse Row storage for maximum spatial locality.
: High-density Compressed Sparse Row storage for maximum spatial locality. Modular Architecture : Clean separation between common utilities, baseline Dijkstra, and optimized DMMSY implementations.
... continue reading