Breaking the Sorting Barrier in Code

Jump to Quickstart

Context

In 2025, Ran Duan et al. published Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. The paper proposes BMSSP – a deterministic $O(m\log^{2/3}n)$-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 + n\log n)$ time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.

This repository contains C++ implementations of both Dijkstra's and BMSSP algorithms, and the infrastructure to benchmark them.

The Algorithm

BMSSP stands for Bounded Multi-Source Shortest Path. The algorithm is tasked with solving the SSSP from a set of sources $S$, with a bound $B$. The top level of the recursion is called with $S = {s}, B = +\infty$, which is equivalent to the full SSSP problem.

Each call of a recursion layer aggregates data in the Prepender data structure, pulling it in batches and delegating to lower recursion levels, with the base case being a mini Dijkstra's algorithm. If a particular recursion level is experiencing too big of a workload, the execution is stopped prematurely, and returns a bound $B' \leq B $, where the processing stopped.

If BMSSP had to be summed up in one sentence, it would most likely be: "Dijkstra's algorithm with batch processing, and means to ensure that the workload is spread evenly".

Implementation

The BMSSP C++ implementation includes a few tweaks. Most notably, it includes non-deterministic elements, such as Hoare's selection algorithm, hashmaps, and hashsets. These are optimizations only, which intend to reduce the constant while staying true to the main idea and the $O(m\log^{2/3}n)$ asymptotic complexity. In turn, Dijkstra's algorithm was kept as simple as possible, while asymptotically optimal.

Results

$\text{Note:}$ For exact calculations, see the SSSP-analysis Google Collab notebook.

Main Conclusion

It is much expected that the algorithm is slower, due to a bigger constant in many cases, as it is relatively more complicated than Dijkstra. However, the results below show that in some non-negligible cases it may be faster. While this doesn't formally prove anything, and is influenced strongly by the chosen implementation, it demonstrates that the algorithm isn't purely theoretical and could perhaps be beneficial in some use cases.

The scaling run

Both algorithms' runtimes were compared on a sample of $n$-vertex $(k \cdot n)$-edge constant degree graphs of average sizes $(n \in {2^{10}, 2^{11}, \ldots, 2^{18}}, k \in {4, 8, \ldots, 64})$. The weight generation method for the graph's edges was also alternated (the $\log$ parameter). Based on the runtime ratios we can make the following observations:

• The log parameter doesn't seem to affect the results much
• The bigger the degree, the "better" (for BMSSP) the ratio
• The ratio has a slow increasing tendency across all degrees

Remark: The results of this run can be recreated by executing ./speedrun.sh.

The deg64 run

After scheduling a bigger run for 64-degree graphs, the observations are even more interesting:

• BMSSP has a smaller runtime, even for graphs with $n = 2^{16} = 65536$ vertices
• BMSSP's advantage appears to fade linearly(?) at the end of the measured range

This makes sense, as the runtime of BMSSP heavily depends on $\lfloor\log^{1/3}n\rfloor$, which will change again at $n = 2^{27}$.

Quickstart

Before running any of the commands below, ensure that you have Bazel installed.

Speedrun - quick benchmarking

To quickly benchmark the BMSSP implementation on a selected range of constant degree graphs, simply run:

./speedrun.sh

This will generate num_samples random graphs for each combination of log_n and degree_list, running Dijkstra's algorithm and BMSSP side by side. The results will be logged in logs/speedrun_log_{timestamp}.csv.

Custom Graphs

To run the BMSSP algorithm on your custom graph, run:

bazel run //bmssp/cc/bmssp_main < path/to/your/graph.in > path/to/result.out

To compare BMSSP with Dijkstra on your custom graph run:

bazel run //validation/cc/compare < path/to/your/graph.in

This implementation accepts graphs in the following format (with 0-indexed vertices):

n_vertices m_edges
u_1 v_1 weight_1
u_2 v_2 weight_2
...
u_m v_m weight_m

All algorithms in this repository output the distances (-1 if unreachable) from vertex 0 to all other vertices, separated by spaces.

Cite

If you find this repository helpful in your research cite simply as:

@misc{SSSP-Code,
  author = {Jan Kwiecinski},
  title = {Breaking the Sorting Barrier in Code},
  year = {2026},
  publisher = {GitHub},
  url = {https://github.com/Jankwi/SSSP-Code}
}

License

MIT