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
Key Features
-
Breaking the Sorting Barrier: Reduces the complexity factor to
$O(\log^{2/3} n)$ , significantly outperforming$O(\log n)$ at scale. - Zero-Allocation Design: 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.
- Modular Architecture: Clean separation between common utilities, baseline Dijkstra, and optimized DMMSY implementations.
- High-Precision Timing: Integrated platform-independent timing for stable performance reporting.
Tests conducted on a modern x86_64 architecture using Clang -O3 with LTO and Fast-Math optimizations.
Note
DMMSY achieves its maximum performance delta on graphs with 250k–1M+ nodes. In the C implementation, the lean DMMSY execution logic (~800ns for 1M nodes) effectively eliminates the sorting bottlenecks found in traditional binary heaps.
The project requires a C99-compliant compiler (Clang recommended for Fat LTO performance).
clang -O3 -march=native -flto -DNDEBUG src/*.c -I include -o dmmsy_benchThe main package provides a comprehensive benchmarking suite that generates random sparse graphs and compares performance across multiple algorithms.
#include "include/common.h"
int main() {
// 1. Generate a sparse graph (1M nodes, 5M edges)
CSRGraph g = random_graph(1000000, 5000000, 100.0);
// 2. Prepare weight and predecessor arrays
weight_t *d = malloc(sizeof(weight_t) * g.n);
node_t *pr = malloc(sizeof(node_t) * g.n);
// 3. Run the Dual-Interval Pivot SSSP
ssp_duan(&g, 0, d, pr);
// 4. Verify results against Dijkstra reference
// ... verification logic ...
free_graph(&g);
return 0;
}-
include/: Common header definitions and API interfaces. -
src/common.c: Core data structures (CSRGraph, Fast4AryHeap). -
src/dijkstra.c: Standard$O(m + n \log n)$ reference implementation. -
src/dmmsy_opt.c: Optimized Duan–Mao–Mao–Shu–Yin algorithm. -
src/benchmark.c: High-precision performance reporting and visualization driver.
Contributions are welcome! If you find a bug, have an optimization suggestion, or want to port to another architecture, please open an issue or pull request.
This project is dual-licensed under the MIT License and Apache License 2.0. See the LICENSE-MIT and LICENSE-APACHE files for details.
- Duan, R., et al. (2025). Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. arXiv:2504.17033
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik.
- ACM Digital Library
- MPI-INF repository