A Deterministic Algorithm that Outpaces Dijkstra on Sparse Graphs

In an arXiv preprint, Breaking the Sorting Barrier for Directed Single-Source Shortest Paths, authors Ran Duan, Longhui Yin et al, present the first deterministic algorithm that beats the classic $O(m+n\log n)$ bound of Dijkstra on sparse directed graphs. 

The researcher's work in the comparison-addition model, the standard for real edge weights, and obtain an $O(m{\log }^{2/3}n)$ time bound. Their approach avoids fully sorting vertices by distance. Instead it carefully limits the number of vertices that must be totally ordered at any time by shrinking a dynamic frontier, then solves a bounded multi-source problem with a divide-and-conquer scheme and targeted relaxations.

Dijkstra with advanced heaps achieves $O(m+n\log n)$ in this model, while for undirected integer weights Thorup achieved linear time and $O(m+n\log \log C)$ for directed graphs with integer weights (Thorup, 1999).

Key Takeaways

• Introduces a deterministic $O(m{\log }^{2/3}n)$ SSSP algorithm for directed graphs with nonnegative real weights in the comparison-addition mode.
  
  
• Breaks the classic sorting barrier underpinning O(n log n) behavior in Dijkstra on sparse graphs by reducing the frontier that must be totally ordered.
  
  
• Defines and solves a bounded multi-source shortest path (BMSSP) subproblem via recursion, with provable correctness and running-time guarantees.
  
  
• Uses a FindPivots procedure to keep only influential frontier vertices and a partial-sorting data structure with batch-prepend to avoid full heap ordering.
  
  
• Provides a deterministic counterpart to earlier randomized improvements on undirected graphs, clarifying when ordering the full vertex set is unnecessary.

Background: Dijkstra, relaxations, and priority queues

Dijkstra's algorithm computes single-source shortest paths in graphs with nonnegative weights by repeatedly selecting the closest unsettled vertex and relaxing its outgoing edges.

The original formulation dates to 1959 (Dijkstra, 1959). Using efficient priority queues, its running time on sparse graphs is classically analyzed as $O(m+n\log n)$, with the Fibonacci heap yielding optimal amortized bounds for the decrease-key operation and achieving this complexity (Fredman and Tarjan, 1987).

Bellman-Ford is a dynamic-programming style algorithm that relaxes all edges in rounds, allowing it to handle negative weights and to detect negative cycles, albeit with a higher O(mn) time bound. Its relaxation paradigm underpins many bounded-expansion routines and is the reference point for the phrase "Bellman-Ford style relaxations" used in this article (Bellman, 1958).

How the approach works

The core idea is to prevent the algorithm from paying a $\log n$ factor for every vertex. In Dijkstra, the priority queue effectively sorts many vertices by distance, and on sparse graphs that sorting cost dominates. 

Duan et al. build a different pipeline by maintaing an unsorted frontier $S$ of candidate vertices whose current estimates fall in a band $[b,B)$, and recursively compute true distances only for those vertices whose shortest paths must cross $S$ before reaching below $B$. This subproblem is called bounded multi-source shortest path (BMSSP).

The BMSSP routine is summarized by Lemma 3.1 in the paper. Given a frontier $S$ with bounded size at a recursion level $l$ and an upper bound $B$, BMSSP returns a refined bound $B^{\prime }$ and a set $U$ of vertices whose distances are now certified. The algorithm ensures $U$ is complete at return. If the workload is small enough, it succeeds with $B^{\prime }=B$; if too large, it makes partial progress and lowers $B$ to $B^{\prime }$.

A key technical device is FindPivots (Algorithm 1 in Section 3). It runs a limited number of Bellman-Ford style relaxations from S (Bellman, 1958). Any vertex reachable with fewer than k hops within the [b, B) band becomes complete immediately. 

For the remaining vertices, each must depend on a frontier vertex whose shortest-path tree within the band has size at least k. Those special frontier vertices are the pivots P.

Importantly, the number of pivots is bounded by |U~|/k, where U~ is the set of vertices of interest under the bound B, so only a 1/k fraction of S needs to be considered at the next recursion step.

The data structure trick

To avoid fully ordering the frontier, the authors design a partial-sorting structure described in Lemma 3.3. Conceptually, it stores key/value pairs (vertex, tentative distance) in two sequences of bounded-size blocks: one for ordinary inserts and one for batch prepends. 

Why this result matters

The comparison-addition model is the right abstraction for real-weighted SSSP. In this model, Dijkstra with advanced heaps is $O(m+n\log n)$, and it has been considered a natural barrier tied to sorting. 

This work shows that when you do not need the full sorted order of all vertices by distance, you can beat that barrier on sparse directed graphs. The algorithm certifies distances without globally ranking everyone at once. That reframes SSSP as a problem where partitioning and bounded exploration can replace total ordering.

The result also complements prior progress. A randomized sub-$O(n\log n)$ algorithm exists for the undirected case when only distances are required. The authors here give a deterministic improvement in directed graphs, filling a long-standing gap. 

Separately, recent work studies when Dijkstra is essentially optimal if you demand the full order of vertices by distance; that highlights that ordering is the expensive part.

What the paper proves and shows

Algorithm 1 "Finding Pivots" formalizes the frontier-shrinking step. It relaxes for $k$ rounds within the $[b,B)$ band, collects a working set $W$ of visited vertices, and identifies $P$, the small set of pivots in $S$ whose trees have at least $k$ vertices inside the band. Either $W$ already grows beyond $k|S|$, giving enough work to proceed, or $P$ has size at most $|W|/k$, ensuring the next level considers only a $1/k$ fraction of the frontier.

Algorithm 2 is the base case: when the recursion level is zero, the frontier collapses to a single complete vertex $u$, and a mini-Dijkstra expands from $u$ until either $k+1$ vertices under the bound are found or none remain. This base case ensures local completeness without touching global structure.

Algorithm 3 is BMSSP itself. Each phase pulls at most $M=2^{l-1}t$ pivots from the partial-sorting structure, recurses on them with a tighter bound, then relaxes edges from the newly completed vertices and batch-prepends any neighbors that now fall into the active band. If the accumulated certified set $U$ exceeds $$\begin{gathered} \mathrm{\Theta }(k \\ ,2^{l}t) \end{gathered}$$ in size, the routine ends early with a lowered bound $B^{\prime }$ to cap work; otherwise it succeeds with $B^{\prime }=B$.

Discussion and interpretation

The paper's central insight is that the cost of SSSP in the comparison-addition model is driven less by relaxations and more by how much ordering you have to do. By carving the problem into bounded bands and working only on pivots, the algorithm minimizes unnecessary ordering. 

The procedure can be viewed as intertwining limited Bellman-Ford style expansions with selective Dijkstra-like exploration, but always within a carefully maintained band to keep the frontier small.

The assumptions are standard: nonnegative real weights and a constant-degree reduction to bound out-degrees by 2 without changing shortest paths. 

The analysis handles both successful and partial executions of BMSSP and proves that per-level work is proportional to the number of newly certified vertices plus low-order overhead.

Conclusion

Duan, Mao, Mao, Shu, and Yin show that directed SSSP does not inherently require sorting all vertices by distance. A deterministic $O(m{\log }^{2/3}n)$ algorithm in the comparison-addition model breaks the long-assumed barrier on sparse graphs by shrinking the frontier, extracting pivots, and solving a bounded multi-source problem recursively. 

For practitioners, the message is that distance certification and full ordering are different goals; if you only need distances, new algorithmic designs can beat the classical priority-queue cost. For researchers, the work opens room to revisit other graph problems where global ordering dominates and to explore whether further improvements are possible under similar divide-and-conquer frameworks.