TL;DR
For 65 years, Dijkstra’s algorithm was the fastest known way to compute single-source shortest paths, and most of us assumed it was optimal. In 2025, a team led by Ran Duan at Tsinghua University proved it isn’t: their deterministic algorithm runs in O(m log^(2/3) n) time and beats Dijkstra on sparse directed graphs. A February 2026 follow-up pushed the bound even lower. The catch, and it’s a big one: on real hardware, plain Dijkstra is still reported to be 3–4× faster, and it’ll stay that way for any graph you’ll ever load into memory.
The barrier that stood since 1959
Edsger Dijkstra published his shortest-path algorithm in 1959. You give it a weighted graph and a starting vertex; it hands back the shortest distance to every other vertex. It has been in every algorithms textbook, every routing stack, and every whiteboard interview since.
The version we actually reason about today pairs Dijkstra’s greedy strategy with a Fibonacci heap, a result from Fredman and Tarjan in 1984 that gets you O(m + n log n) time for m edges and n vertices. On a dense graph, where m is close to n², the m term dominates and the algorithm is basically linear in the input. On a sparse graph, where each vertex has a handful of edges and m is roughly proportional to n, the n log n piece takes over. That log-n factor is the tax, and for decades it looked like a tax you had to pay.
Here is why the tax exists. Dijkstra settles vertices in strictly increasing order of distance: closest first, then next-closest, and so on. To always pull out the current minimum, it keeps its frontier in a priority queue and pays O(log n) per extraction. Do that n times and you have effectively sorted all n vertices by distance. Sorting n comparable things has a known lower bound of Ω(n log n), so as long as your algorithm produces a fully sorted output, you can’t dip below it. Researchers called this the sorting barrier, and the open question was whether shortest paths actually require it, or whether the sorting was just an accident of how Dijkstra happens to work.
I wanted to feel the barrier before reading how it fell, so I dropped a textbook Dijkstra into a file and timed it. Here is the whole thing:
import heapq
def dijkstra(graph, source):
dist = {v: float('inf') for v in graph}
dist[source] = 0
pq = [(0, source)] # the heap IS the sorting barrier
settled = set()
while pq:
d, u = heapq.heappop(pq)
if u in settled:
continue
settled.add(u)
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
g = {
'A': [('B', 4), ('C', 1)],
'B': [('D', 1)],
'C': [('B', 2), ('D', 5)],
'D': [('E', 3)],
'E': [],
}
print("distances from A:", dijkstra(g, 'A'))
Running it prints the shortest distance from A to everything else:
distances from A: {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}
The direct edge A→B costs 4, but the detour A→C→B costs 1 + 2 = 3, so the algorithm picks 3. Standard stuff. Then I generated a random sparse graph (average degree 3, so m ≈ 3n) and let the same function loose on it:
n= 100,000 m= 299,999 dijkstra: 1.11s
n=1,000,000 m=2,999,999 dijkstra: 16.92s
Ten times the vertices, roughly fifteen times the wall-clock. That super-linear creep is the log n factor showing up in a real profiler (pure Python inflates the constants, so read these as shape rather than a benchmark). Every one of those seconds is the heap keeping the frontier in perfect sorted order. The Duan result asks a sharp question: what if it didn’t have to?
What Duan and his co-authors actually did
The paper is Breaking the Sorting Barrier for Directed Single-Source Shortest Paths by Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin. It won a Best Paper Award at STOC 2025, the top theory conference, held in Prague that June. The headline result: a deterministic O(m log^(2/3) n)-time algorithm for single-source shortest paths on directed graphs with non-negative real weights, in the comparison-addition model. On sparse graphs that’s asymptotically below O(m + n log n), so it’s the first algorithm to prove Dijkstra isn’t optimal for this problem.
The trick is to stop insisting on a fully sorted frontier. You don’t need to know the exact order in which the next thousand vertices settle. You only need to keep finding correct shortest distances. So instead of one global priority queue, the algorithm runs a recursive routine the authors call BMSSP, for Bounded Multi-Source Shortest Path. Each call is handed a distance bound B and told: find every shortest path shorter than B, starting from a set of sources rather than a single one. It splits that job into smaller bounded sub-problems and recurses.
One blogger summed up the shape of it in a line I liked: “Dijkstra is to BMSSP as binary-tree sort is to merge sort.” Dijkstra grows one ordered structure incrementally; BMSSP divides, conquers, and merges bounded pieces, and never pays for a total order it won’t use.
The move that keeps the whole thing cheap is frontier reduction. Before recursing, a step called FindPivots runs a few rounds of Bellman-Ford-style relaxation out from the current frontier, just a handful of layers rather than the full graph. Most vertices it touches turn out to hang off a small number of “pivot” vertices that sit at the root of large shortest-path trees. The algorithm keeps only those pivots and drops the rest from the active set, shrinking the frontier by a factor of roughly k each time. A smaller frontier means fewer things to track, and fewer things to sort. Sorting was the whole tax. Stack about log^(2/3) n of these recursion levels on top of each other and the log-n cost collapses to log^(2/3) n.
That Bellman-Ford cameo is the satisfying part. Bellman-Ford is the other shortest-path algorithm everyone learns: slower, brute-force, relaxing every edge over and over. On its own it loses to Dijkstra badly. Bolted on as a frontier-pruning pre-pass, it’s exactly the tool that lets you skip the sorting Dijkstra can’t. The winning design fuses the two classics rather than replacing either.
The 2026 sequel went further
Barriers, once cracked, tend to keep cracking. In February 2026 an overlapping group (Ran Duan, Xiao Mao, Xinkai Shu, and Longhui Yin) posted A Faster Directed Single-Source Shortest Path Algorithm. Its full running time is O(m√(log n) + √(mn log n log log n)), which on sparse graphs simplifies to O(m √(log n · log log n)) and drops the exponent on the log from 2/3 toward 1/2. Same problem, same deterministic setting, tighter analysis and a refined recursion. Less than a year after the first paper, the frontier had already moved.
| Algorithm | Result year | Time on sparse directed graphs | Beats Dijkstra? |
|---|---|---|---|
| Dijkstra + Fibonacci heap | 1984 (Fredman–Tarjan) | O(m + n log n) | — (the baseline) |
| Duan, Mao, Mao, Shu, Yin (BMSSP) | 2025 | O(m log^(2/3) n) | Yes, asymptotically |
| Duan, Mao, Shu, Yin | 2026 | O(m √(log n · log log n)) | Yes, further still |
Neither result is a small tweak. Both are genuine progress on a problem that had not moved in decades, and the theory community treats them as landmark work. If you study algorithms, this is the most exciting thing to happen to shortest paths in a long time.
Where the speedup disappears in practice
Now the honest column of the ledger. “Faster than Dijkstra” is true in the asymptotic, worst-case, big-O sense, and that sense hides enormous constant factors.
A November 2025 paper by Lucas Castro, Thailsson Clementino, and Rosiane de Freitas, Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm, did the unglamorous work of actually coding it up and racing it against Dijkstra. They tested sparse random graphs, grids, and U.S. road networks up to 10 million vertices. Their finding is blunt: Dijkstra’s algorithm stays 3 to 4 times faster in every scenario they tried. The recursion, the pivot bookkeeping, and the Bellman-Ford passes carry so much overhead that the asymptotic win never gets a chance to pay off. By their estimate, a graph would need to exceed 10^67 vertices before the worst-case bound overtakes Dijkstra in practice. There are about 10^80 atoms in the observable universe. You’re never going to hit that input size.
None of this diminishes the theory. A worst-case upper bound is a statement about what is possible, and lowering it redraws what the next decade of research takes for granted. Practical speedups have a long history of arriving years after the asymptotic breakthrough that made them thinkable. Someone finds the idea that removes the constants, and a “useless” bound becomes a real library. The 2025 result opened that door. Whether anyone walks a fast version through it is a separate, open problem.
What this changes for my own code
Concretely, for the work I actually ship: nothing, and I think that is the right takeaway rather than a disappointing one. When I need shortest paths, I still reach for Dijkstra with a binary heap, or A* when I have a decent distance heuristic, or contraction hierarchies when I’m precomputing a road network and can afford the setup. Those are still the fastest tools for graphs that fit on a machine.
What did change is how I read a complexity result. Sitting next to my own timing numbers, a million-node graph chewing up 16.9 seconds with most of it inside the heap, the BMSSP paper is a clean demonstration that a bound you’ve quietly accepted as a law can just be a habit. The sorting barrier felt like a law of nature. It turned out to be a quirk of one particular algorithm, and the problem itself never demanded it. Worth keeping in mind the next time some O(n log n) in your own stack feels permanent. It might only be waiting for the right recursion.
If you want to reproduce the feel of it, the Dijkstra snippet above runs as-is on any Python 3, and the two papers below are both readable if you’re comfortable with graph proofs. Start with the 2025 one; the introduction alone explains the sorting barrier better than most textbooks. For a broader tour of how algorithmic lower bounds have been falling lately, I wrote up the four color theorem dropping to O(n log n), another 2026 result where a barrier everyone treated as settled quietly gave way. And if your interest in “doing less work” is more about models than graphs, the same instinct drives efficient LLM reasoning and sparse attention, where the trick is likewise skipping computation you were told you needed.
FAQ
Is there an algorithm faster than Dijkstra?
Yes, as of 2025. The Duan et al. algorithm runs in O(m log^(2/3) n) time on directed graphs with non-negative weights, which is asymptotically faster than Dijkstra’s O(m + n log n) on sparse graphs. A 2026 follow-up is faster still. In everyday practice, though, well-tuned Dijkstra remains 3–4× quicker on any real-world graph, because the new algorithm’s constant factors are huge.
What is the new shortest path algorithm called?
The paper doesn’t brand it with a catchy name, but its core recursive routine is BMSSP, short for Bounded Multi-Source Shortest Path. People usually refer to it as “the Duan et al. algorithm” or “the algorithm that broke the sorting barrier.”
How does the new shortest-path algorithm work?
It avoids fully sorting the frontier. Dijkstra settles vertices in exact distance order using a priority queue, which forces an Ω(n log n) sorting cost. BMSSP instead solves many bounded shortest-path sub-problems recursively, and before each recursion a FindPivots step runs a few Bellman-Ford relaxation rounds to shrink the frontier down to a small set of “pivot” vertices. Fewer vertices to track means less sorting, and the log-n factor drops to log^(2/3) n.
Who discovered the new shortest path algorithm?
A team led by Ran Duan at Tsinghua University, with co-authors Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin. They presented it at STOC 2025 in Prague, where it won a Best Paper Award.
Should I replace Dijkstra with it in production?
No. For graphs that fit in memory, which is essentially all of them, Dijkstra with a good heap, A*, or contraction hierarchies will beat it comfortably. The new algorithm is a statement about worst-case complexity, and it won’t drop into your stack as a speedup. Treat it as proof the barrier is breakable rather than as your next routing library.
Sources
- Breaking the Sorting Barrier for Directed Single-Source Shortest Paths — arXiv:2504.17033 — the original STOC 2025 Best Paper this post summarizes
- Breaking the Sorting Barrier — ACM STOC 2025 proceedings — the peer-reviewed conference version
- A Faster Directed Single-Source Shortest Path Algorithm — arXiv:2602.07868 — the February 2026 follow-up improving the bound
- Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm — arXiv:2511.03007 — the benchmark study finding Dijkstra 3–4× faster in practice
Bottom line
Dijkstra’s 65-year reign as the provably fastest way to find shortest paths is over, at least on paper. The Duan team showed the sorting barrier was never a law of the problem, only a feature of one very good algorithm, and they did it with a clever hybrid of Dijkstra and the humble Bellman-Ford. That’s a beautiful result and it deserves the award it got. It also won’t touch your production routing code for years, if ever, and the researchers who benchmarked it are the first to say so. Keep shipping Dijkstra. Just know, now, that it was never the finish line.