Can a New Algorithm Really Beat Dijkstra? Inside the Breakthrough Shortest‑Path Method

Problem Background

The single‑source shortest‑path problem asks for the minimum‑weight distances from a source vertex to every other vertex in a weighted graph. Classical solutions such as Dijkstra’s algorithm expand outward from the source, repeatedly selecting the closest unsettled vertex. Each selection implicitly requires sorting (or a priority queue), which creates a fundamental "sorting bottleneck" that limits the overall running time.

Sorting Bottleneck in Prior Work

Since the 1984 improvement by Tarjan and collaborators, the best known bounds for general‑weight graphs are achieved by algorithms that still rely on sorting the frontier. Any further asymptotic speed‑up must avoid this step.

New Algorithm for Undirected Graphs

Professor Duan Ran (Tsinghua University) and his team introduced a clustering‑based approach that completely eliminates the sorting step:

At each iteration the frontier vertices are partitioned into clusters.

Only a single representative vertex from each cluster is examined, dramatically reducing the number of candidates.

The algorithm maintains correctness of the distance labels despite not processing vertices in strict distance order.

The resulting method runs faster than any known sorting‑based algorithm on undirected graphs and is deterministic after a later refinement that removed randomization.

Extension to Directed Graphs

To handle arbitrary directed graphs the authors combine the clustering idea with a staged use of the Bellman‑Ford algorithm:

Bellman‑Ford is executed only on carefully chosen sub‑steps to identify high‑impact vertices (the “critical” nodes).

These critical nodes guide the clustering expansion, so the algorithm never needs a global priority queue.

The hybrid procedure preserves correctness for graphs with any edge weights and matches or slightly exceeds the performance of the best optimized Dijkstra variants.

Technical Highlights

Complexity: The undirected version achieves sub‑linear overhead per iteration compared with the $O(m\log n)$ bound of heap‑based Dijkstra, effectively breaking the sorting lower bound.

Determinism: An additional derandomization step replaces the original randomized cluster selection, yielding a fully deterministic algorithm.

Modularity: The method consists of three reusable modules – clustering, critical‑node detection (via limited Bellman‑Ford), and layered expansion – which can be tuned independently.

References

Primary paper (arXiv): https://arxiv.org/abs/2504.17033 STOC Best Paper announcement: https://dl.acm.org/doi/10.1145/28869.28874 Follow‑up work on undirected graphs:

https://arxiv.org/abs/2307.04139