One-sentence Summary

The authors propose a deterministic $O(m \log^{2/3} n)$O(mlog2/3n)-time algorithm for SSSP on directed graphs with non-negative real weights, breaking Dijkstra's long-standing $O(m + n \log n)$O(m+nlogn) bound for sparse graphs and demonstrating that Dijkstra's algorithm is not optimal in the comparison-addition model.

Key Contributions

• This work presents the first deterministic algorithm to break the long-standing $O(m + n \log n)$O(m+nlogn) time bound of Dijkstra's algorithm for single-source shortest paths (SSSP) in directed graphs with real non-negative edge weights, demonstrating that Dijkstra's approach is not optimal in the comparison-addition model.

• The key technical insight is a recursive divide-and-conquer framework that combines Dijkstra's frontier exploration with Bellman-Ford-style relaxation, enabling a novel frontier reduction technique that limits the number of active vertices requiring sorting to $O(|\widetilde{U}| / \log^{\Omega(1)} n)$O(∣U∣/logΩ(1)n), thereby circumventing the $\Omega(n \log n)$Ω(nlogn) sorting barrier.

• The resulting algorithm runs in $O(m \log^{2/3} n)$O(mlog2/3n) time on sparse graphs, marking the first deterministic improvement over Dijkstra's bound for directed graphs and extending the class of graph problems that can bypass comparison-based sorting lower bounds.

Introduction

The authors address the long-standing challenge of solving single-source shortest paths (SSSP) in directed graphs faster than the $O(n \log n)$O(nlogn) sorting barrier, which arises naturally in the comparison-addition model where edge weights are real numbers. While prior work has broken this barrier for undirected graphs using advanced data structures and randomized techniques, no such improvement was known for directed graphs, where Dijkstra's algorithm remains the standard with $O(m + n \log n)$O(m+nlogn) time complexity. The key limitation of existing approaches is their reliance on vertex ordering by distance, which inherently requires sorting and thus incurs the $n \log n$nlogn cost. The authors’ main contribution is a breakthrough randomized algorithm that breaks the sorting barrier for directed SSSP, achieving a runtime of $O(m \sqrt{\log n \log \log n})$O(mlognloglogn​), thereby demonstrating that the $n \log n$nlogn bottleneck is not fundamental in directed graphs. This result advances the theoretical understanding of SSSP and opens new pathways for efficient graph algorithms in the comparison-addition model.

Method

The authors present a deterministic algorithm for single-source shortest paths (SSSP) on directed graphs with non-negative real edge weights, achieving an $O(m \log^{2/3} n)$O(mlog2/3n) time complexity, which breaks the long-standing $O(m + n \log n)$O(m+nlogn) barrier of Dijkstra's algorithm on sparse graphs. The core of the approach lies in a divide-and-conquer framework that recursively partitions the graph based on distance bounds, avoiding the need for a full sorting of vertices at each step. The algorithm operates on a constant-degree graph, where each vertex has bounded in-degree and out-degree, achieved through a standard transformation that preserves shortest paths while ensuring constant-degree properties.

The main computational engine is the Bounded Multi-Source Shortest Path (BMSSP) subroutine, which is designed to compute shortest paths from a set of source vertices $S$S to all vertices within a given distance bound $B$B. The key insight is to maintain a dynamic frontier of vertices that are not yet fully processed, but whose shortest paths must pass through the current set of complete vertices in $S$S. The algorithm avoids the $O(n \log n)$O(nlogn) sorting bottleneck inherent in Dijkstra's priority queue by recursively shrinking this frontier. This is achieved through a procedure called FINDPIVOTS, which identifies a smaller set of "pivots" from $S$S that are sufficient to guide the recursive computation. Specifically, FINDPIVOTS performs $k$k rounds of edge relaxation from the vertices in $S$S, where $k = \lfloor \log^{1/3} n \rfloor$k=⌊log1/3n⌋. After these relaxations, any vertex $v$v whose shortest path from the source contains at most $k$k vertices from the frontier is guaranteed to be complete. The remaining vertices, whose shortest paths require more than $k$k steps through the frontier, must be rooted in a shortest path tree of size at least $k$k originating from a vertex in $S$S. The pivots are precisely the roots of these large trees, and their number is bounded by $|U|/k$∣U∣/k, where $U$U is the set of vertices of interest.

[[IMG:|Framework diagram]]

The BMSSP algorithm itself is structured as a recursive procedure with $l$l levels, where $l$l is a parameter related to the recursion depth. At each level $l$l, the algorithm first calls FINDPIVOTS to obtain a set of pivots $P$P and a set of vertices $W$W that are either complete or depend on the pivots. It then initializes a data structure $\mathcal{D}$D, which is a block-based linked list designed to efficiently manage key/value pairs (vertex, distance) and support operations like insertion, batch prepending, and pulling the smallest elements. The data structure is initialized with the pivots $P$P as keys, associated with their current distance estimates. The algorithm then iteratively pulls the $M = 2^{(l-1)t}$M=2(l−1)t vertices with the smallest distances from $\mathcal{D}$D, where $t = \lfloor \log^{2/3} n \rfloor$t=⌊log2/3n⌋, and recursively calls BMSSP on each such subset. After processing the recursive call, the algorithm relaxes all outgoing edges from the newly completed vertices $U_i$Ui​ and inserts their neighbors into $\mathcal{D}$D based on their new distance estimates. A crucial optimization is the use of batch prepending to efficiently reinsert vertices that were previously processed but may now have improved distance estimates. The recursion terminates when the total number of processed vertices $|U|$∣U∣ exceeds $k2^{lt}$k2lt, indicating a partial execution, or when $\mathcal{D}$D becomes empty, indicating a successful execution.

[[IMG:|Data structure diagram]]

The algorithm's correctness is established by showing that at each recursive call, the set of incomplete vertices with distance less than $B$B is contained within the union of the shortest path trees rooted at the current set of sources $S$S. The data structure $\mathcal{D}$D ensures that vertices are processed in increasing order of their distance estimates, and the recursive calls are designed to cover all vertices in the relevant distance range. The time complexity analysis leverages the fact that the number of vertices processed at each level of recursion is bounded, and the work done per vertex is reduced by a factor of $\log^{1/3} n$log1/3n due to the frontier reduction. The total running time is dominated by the cost of the FINDPIVOTS procedure and the operations on the data structure $\mathcal{D}$D, which are shown to sum to $O(m \log^{2/3} n)$O(mlog2/3n) when the parameters $k$k and $t$t are set appropriately.