Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin
cs.DS
2025-04-24
Deterministic O(m log^{2/3} n) directed SSSP with real non-negative weights, first to beat Dijkstra's O(m+n log n) on sparse graphs in the comparison-addition model.
On directed graphs with non-negative weights, the textbook algorithm for single-source shortest paths is Dijkstra. With a Fibonacci heap or a relaxed heap it runs in O(m + n log n) in the comparison-addition model. That model allows only comparisons and additions on edge weights, each in unit time: the right cost model for real weights, and the wrong one for bit tricks on integers.
Dijkstra also emits vertices in distance order. Haeupler, Hladík, Rozhoň, Tarjan and Tětek proved that if the algorithm must output that order, Dijkstra is optimal: the Ω(n log n) sorting lower bound stays. If only distances are required, Duan, Mao, Shu and Yin already had a randomized O(m √(log n log log n)) algorithm for undirected graphs in 2023, faster than O(n log n) on sparse instances. Directed graphs still sat behind the barrier.
The sorting barrier has fallen for other graph problems. MST went from O(m log log n) to randomized linear time; bottleneck paths and single-source nondecreasing paths are also below sorting. Directed SSSP with real weights, on sparse graphs, had been Dijkstra since 1959.
The construction mixes Dijkstra's heap with Bellman-Ford's "relax k steps, no sorting", then wraps both in divide-and-conquer.
While Dijkstra runs, the heap holds a frontier S. If a vertex u is still incomplete (the current estimate d̂[u] exceeds the true distance d(u)), its shortest path visits some already-complete vertex in S. Dijkstra always extracts the closest vertex in S, which must be complete, and relaxes its outgoing edges. The bottleneck is that S can have Θ(n) vertices. Repeatedly taking the minimum maintains a total order, so Ω(n log n) will not go away.
The move is to shrink the frontier. To compute every distance below a bound B, let Ũ be the vertices with d(u)<B whose shortest path visits S. With k = log^{Ω(1)} n there are two cases:
The algorithm does not maintain Dijkstra's moving frontier. It uses a divide-and-conquer with log n / t levels, parameters k = ⌊log^{1/3} n⌋ and t = ⌊log^{2/3} n⌋, so the depth is O(log^{1/3} n). A naive implementation would still spend Θ(t) per frontier vertex per level, which is Θ(log n) per vertex. Spend that Θ(t) only on pivots, about a 1/log^{Ω(1)} n fraction of the frontier, and the per-vertex cost drops to log n / log^{Ω(1)} n.
The subproblem is bounded multi-source shortest path (BMSSP). Given a level l, a bound B, and a frontier S with |S| ≤ 2^{lt}, every incomplete vertex with d(v)<B has a shortest path through some complete vertex in S. BMSSP returns a new bound B' ≤ B and a set U that is complete at the end. Either the call succeeds (B'=B, everything in range is done) or it stops early on a large workload (|U| = Θ(k · 2^{lt}), B'<B). The top-level call is BMSSP(⌈log n / t⌉, {s}, ∞). |U| ≤ n is o(k n), so the call must succeed and all distances are found.
FindPivots relaxes k steps from S and builds W. If |W| exceeds k|S|, the whole of S is returned as the pivot set. Otherwise the current estimates form a forest, and P collects roots whose trees have at least k nodes, so |P| ≤ |W|/k. Constant out-degree keeps |W| = O(k|S|) even on the early-exit path.
A partial-sorting structure avoids sorting the whole frontier. Two sequences of blocks hold at most M key/value pairs each, with a balanced tree on block upper bounds. Insert is amortized O(max{1, log(N/M)}). BatchPrepend inserts a batch of values known to be smaller than anything already stored. Pull returns at most M smallest keys and a separating bound. At level l, M = 2^{(l-1)t}, so Insert is amortized O(t) and BatchPrepend is O(log log n) per vertex.
The input is first turned into a constant-degree graph: each vertex becomes a zero-weight cycle, original edges attach to the matching cycle vertices, in- and out-degree at most 2, and both n and m become O(m). Path lengths are ordered lexicographically by (length, hop count, reversed vertex sequence) so ties break in O(1) and the shortest-path tree stays a tree.
This is a theory paper. There is no implementation and no wall-clock experiment.
Theorem: in the comparison-addition model, directed graphs with real non-negative weights admit a deterministic O(m log^{2/3} n)-time SSSP algorithm.
On sparse graphs (m = Θ(n)), Dijkstra is O(n log n) and this is O(n log^{2/3} n). Because the 2023 undirected result is randomized, this is also the first deterministic algorithm to break O(m+n log n) on undirected graphs.
The runtime skeleton: FindPivots costs O(n k) per recursion level, there are O(log n / t) levels, product O(n k log n / t) = O(n log^{2/3} n). Pivot insertions into the block structure cost O(n t / k) per level and still O(n log^{2/3} n) in total. Each edge triggers a direct Insert only once in the whole recursion tree, for O(m(t + log k)) = O(m log^{2/3} n). After the constant-degree reduction n and m are the same order, so the bound is O(m log^{2/3} n).
Comparisons have to stay inside the model. With integer weights on the word RAM, undirected SSSP is already linear (Thorup) and directed SSSP is O(m + n log log min{n, C}) for maximum weight C. Negative weights are a different line: near-linear for negative integers, currently subcubic for negative reals. None of those numbers compete with real non-negative weights under comparison-addition.
On sparse directed graphs, real non-negative weights, distances only: Dijkstra is not optimal. That sentence now has a deterministic algorithm behind it, for the first time since 1959.
The sentence it does not touch: if the output must be the distance order, Dijkstra remains optimal. The gain is "do not sort everything". In production, Fibonacci-heap Dijkstra is still the tool. BMSSP recursion, pivots, and the block list are not a drop-in for a graph library, and the paper never claims they are.
For algorithm designers the portable piece is frontier reduction: a few Bellman-Ford steps clear short dependencies, the remaining work concentrates on a few large-tree roots, then recurse. The hierarchical / pivot idea from bottleneck paths is what finally opens the directed SSSP sorting barrier.
Non-negative weights only. Negative weights, integer RAM, and approximation live in other models.
The output has no distance order. If the order is required, the Haeupler et al. lower bound still pins Dijkstra.
The constant-degree reduction blows the vertex count up to O(m); n in the analysis is the transformed size. The log^{2/3} exponent is the balance of k and t. Whether a better deterministic exponent exists is open: there is no matching lower bound. There is also no implementation, so constants, recursion overhead, and the engineering cost of the block list are unknown.
Comparison-addition forbids bit operations on weights, so Thorup-style RAM heaps do not apply. Unique path lengths are an assumption discharged by the lexicographic tie-break, not by claiming real instances have no ties. An implementation still has to carry that comparator.