vix.ing · top · new · best · stats · spec

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

A new deterministic algorithm solves single-source shortest paths in O(mlog2/3n) time, beating Dijkstra's complexity on sparse graphs.

2025/04/23 by Ran Duan, Duan, Ran, Jiayi Mao +7 · 54 voices · 14 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #Machine Learning and Algorithms #DNA and Biological Computing

paper · pdf · doi:10.48550/arxiv.2504.17033

Abstract

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 = 106–107, 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.

Summary

The authors present a deterministic algorithm for single-source shortest paths (SSSP) on directed graphs with non-negative real edge weights. By combining recursive partitioning and a 'pivot' reduction technique to limit the size of the frontier, they achieve a time complexity of O(mlog2/3n), proving that Dijkstra's algorithm is not optimal for SSSP.

machine-generated · gemma4:31b

In simple words

Finding the shortest way from one spot to all others in a map is usually done by sorting spots by distance. This takes a certain amount of time that experts thought could not be beaten. The authors found a new way to do this without sorting everything perfectly. They use a trick to group spots and only focus on a few important ones, which makes the process faster.

machine-generated · gemma4:31b

Outline

machine-generated · gemma4:31b

Argument

  1. Dijkstra's algorithm is limited by the need to maintain a total order (sorting) of vertices in the frontier, leading to Ω(n log n) complexity.
    Citation: Haeupler et al.
  2. The size of the frontier can be reduced if we only care about distances below a certain bound B.
    Assumption/Logic: If the number of vertices with distance < B is small, the frontier is naturally small; otherwise, most vertices are reachable via a few 'pivots'.
  3. A recursive partitioning technique (BMSSP) can be used to process vertices in groups rather than one by one.
    Proof: The BMSSP lemma and the associated algorithm.
  4. Using a custom block-based linked list data structure allows for efficient insertions and 'pull' operations without full sorting.
    Proof: Lemma on the partition data structure.
  5. The combination of pivot reduction, recursive partitioning, and the specialized data structure reduces total time to O(mlog2/3n).
    Proof: Time Complexity Analysis section.

machine-generated · gemma4:31b

Assumptions

machine-generated · gemma4:31b

Claims

machine-generated · gemma4:31b

Proof sketch

  1. The authors use a recursive divide-and-conquer approach to partition vertices by distance, avoiding the full sorting required by Dijkstra's algorithm.
  2. They introduce 'pivots'—a small subset of frontier vertices that root large shortest-path trees—to reduce the size of the priority queue at each level.
  3. A custom block-based data structure supports efficient batch insertions and pulls to maintain these pivots without incurring a full log n cost per vertex.
  4. The algorithm alternates between Bellman-Ford-like relaxations for short paths and recursive calls for longer paths, ensuring that only a fraction of vertices are processed at each level.
  5. By setting parameters k = log1/3n and t = log2/3n, the total complexity is reduced to O(mlog2/3n).

machine-generated · gemma4:31b

Citations

Cited by

Discussions

Related