The Ultimate Breakthrough: Shattering the Sorting Barrier in Shortest-Path Algorithms
Hello everyone, and welcome to another episode of “Why Are We Still Talking About Dijkstra’s Algorithm in 2025?” Today, we’re diving into the latest Quanta Magazine article, “New Method Is the Fastest Way To Find the Best Routes.” Spoiler alert: it’s about finding the shortest path in a network, and apparently, this is still a thing that keeps computer scientists up at night. Who knew?
Let’s start with the basics. The article kicks off by reminding us that if you want to solve a tricky problem, it helps to get organized. Groundbreaking stuff, really. They even suggest breaking the problem into pieces and tackling the easiest ones first. I mean, who would have thought? Next, they’ll be telling us to wash our hands before surgery.
The canonical problem in question is finding the shortest route to every point in a network. It’s like moving to a new city and figuring out the best way to get to work, the gym, and the supermarket. Except, instead of using Google Maps like a normal person, we’re apparently supposed to care about the theoretical underpinnings of how Google Maps works. Because, you know, that’s what everyone thinks about while stuck in traffic.
The article then introduces us to Mikkel Thorup, a computer scientist at the University of Copenhagen, who describes the shortest-paths problem as “a beautiful problem that anyone in the world can relate to.” Sure, Mikkel, if by “anyone” you mean people who get excited about graph theory at parties. The rest of us are just trying to avoid potholes.
Now, here’s where it gets interesting—or as interesting as this topic can get. The article explains that traditional algorithms, like Dijkstra’s, sort the points by distance as they go, and there’s a fundamental speed limit for any algorithm that follows this approach: you can’t go any faster than the time it takes to sort. This is known as the “sorting barrier.” Apparently, this has been a thorn in the side of computer scientists for decades. I can only imagine the sleepless nights, the cold sweats, the existential dread. “Honey, I can’t come to bed yet. The sorting barrier is haunting me again.”
Forty years ago, researchers hit this speed limit, and any further improvement would have to come from an algorithm that avoids sorting. Enter the hero of our story: a team of researchers who have devised a new approach that doesn’t sort and runs faster than any algorithm that does. It’s like discovering a new surgical technique that doesn’t require anesthesia—risky, but potentially revolutionary.
The article quotes Robert Tarjan, a computer scientist at Princeton University, who says, “The authors were audacious in thinking they could break this barrier. It’s an amazing result.” Audacious, indeed. I mean, who wakes up one day and decides, “You know what? I’m going to break a 40-year-old computational barrier today.” Most of us are just trying to break our personal best on Wordle.
The article then delves into the technical details, using the language of graphs—networks of points, or nodes, connected by lines. Each link between nodes is labeled with a number called its weight, which can represent the length of that segment or the time needed to traverse it. There are usually many routes between any two nodes, and the shortest is the one whose weights add up to the smallest number. Given a graph and a specific “source” node, an algorithm’s goal is to find the shortest path to every other node. Riveting stuff.
They even include a graphic, which, of course, I can’t see, but I’m sure it’s as exciting as a colonoscopy prep chart. The article then reminds us that Dijkstra’s algorithm, devised in 1956, starts at the source and works outward step by step. It’s an effective approach because knowing the shortest path to nearby nodes can help you find the shortest paths to more distant ones. But because the end result is a sorted list of shortest paths, the sorting barrier sets a fundamental limit on how fast the algorithm can run.
In 1984, Tarjan and another researcher optimized Dijkstra’s algorithm so that it hit this speed limit. Any further improvement would have to come from an algorithm that avoids sorting. In the late 1990s and early 2000s, Thorup and other researchers devised algorithms that broke the sorting barrier, but they needed to make assumptions about weights. Nobody knew how to extend their techniques to arbitrary weights. It seemed they’d hit the end of the road. Or, in medical terms, they’d reached a dead end in the circulatory system.
But then, along comes Duan, a computer scientist who apparently doesn’t know when to quit. He’d long dreamed of building a shortest-paths algorithm that could break through the sorting barrier on all graphs. Last fall, he finally succeeded. The key was to focus on where the algorithm goes next at each step. Dijkstra’s algorithm takes the region that it has already explored in previous steps and decides where to go next by scanning this region’s “frontier”—all the nodes connected to its boundary. This doesn’t take much time at first, but it gets slower as the algorithm progresses.
Duan envisioned grouping neighboring nodes on the frontier into clusters. He would then only consider one node from each cluster. With fewer nodes to sift through, the search could be faster at each step. The algorithm also might end up going somewhere other than the closest node, so the sorting barrier wouldn’t apply. But ensuring that this clustering-based approach actually made the algorithm faster rather than slower would be a challenge. It’s like trying to perform a heart transplant with fewer instruments—sure, it’s faster, but is it better?
Duan fleshed out this basic idea over the following year, and by fall 2022, he was optimistic that he could surmount the technical hurdles. He roped in three graduate students to help work out the details, and a few months later they arrived at an algorithm that broke the sorting barrier for any weights, but only on so-called undirected graphs. In undirected graphs, every link can be traversed in both directions. Computer scientists are usually more interested in the broader class of graphs that feature one-way paths, but these “directed” graphs are often trickier to navigate.
The article then introduces us to Mao, a computer science graduate student at Stanford University, who heard Duan give a talk about the undirected-graph algorithm at a conference in California. He struck up a conversation with Duan, whose work he’d long admired. “I met him for the first time in real life,” Mao recalled. “It was very exciting.” I can only imagine the fanboy moment. “Oh my god, it’s Duan! Can you sign my adjacency matrix?”
After the conference, Mao began thinking about the problem in his spare time. Meanwhile, Duan and his colleagues were exploring new approaches that could work on directed graphs. They took inspiration from another venerable algorithm for the shortest-paths problem, called the Bellman-Ford algorithm, that doesn’t produce a sorted list. At first glance, it seemed like an unwise strategy, since the Bellman-Ford algorithm is much slower than Dijkstra’s.
“Whenever you do research, you try to take a promising path,” Thorup said. “I would almost call it anti-promising to take Bellman-Ford, because it looks completely like the stupidest thing you could possibly do.” Well, sometimes the stupidest thing turns out to be the smartest. Just ask anyone who’s ever tried leech therapy.
Duan’s team avoided the slowness of the Bellman-Ford algorithm by running it for just a few steps at a time. This selective use of Bellman-Ford enabled their algorithm to scout ahead for the most valuable nodes to explore in later steps. These nodes are like intersections of major thoroughfares in a road network. “You have to pass through [them] to get the shortest path to a lot of other stuff,” Thorup said.
In March 2024, Mao thought of another promising approach. Some key steps in the team’s original approach had used randomness. Randomized algorithms can efficiently solve many problems, but researchers still prefer nonrandom approaches. Mao devised a new way to solve the shortest-paths problem without randomness. He joined the team, and they worked together over the following months via group chats and video calls to merge their ideas. Finally, in the fall, Duan realized they could adapt a technique from a 2018 paper that broke the sorting barrier for a different graph problem. That technique was the last piece they needed for an algorithm that ran faster than Dijkstra’s on both directed and undirected graphs.
The finished algorithm slices the graph into layers, moving outward from the source like Dijkstra’s. But rather than deal with the whole frontier at each step, it uses the Bellman-Ford algorithm to pinpoint influential nodes, moves forward from these nodes to find the shortest paths to others, and later comes back to other frontier nodes. It doesn’t always find the nodes within each layer in order of increasing distance, so the sorting barrier doesn’t apply. And if you chop up the graph in the right way, it runs slightly faster than the best version of Dijkstra’s algorithm. It’s considerably more intricate, relying on many pieces that need to fit together just right. But curiously, none of the pieces use fancy mathematics.
“This thing might as well have been discovered 50 years ago, but it wasn’t,” Thorup said. “That makes it that much more impressive.” Or, you know, it makes you wonder what everyone was doing for the last 50 years. Maybe they were too busy playing Minesweeper.
Duan and his team plan to explore whether the algorithm can be streamlined to make it even faster. With the sorting barrier vanquished, the new algorithm’s runtime isn’t close to any fundamental limit that computer scientists know of. “Being an optimist, I would not be surprised if you could take it down even further,” Tarjan said. “I certainly don’t think this is the last step in the process.” Of course not. Because why would we ever stop obsessing over the shortest-paths problem? It’s the gift that keeps on giving.
So, what’s the takeaway here? Well, if you’re a computer scientist, this is apparently a big deal. If you’re anyone else, it’s a reminder that there are people out there who spend their lives thinking about things you didn’t even know existed. And for that, we should be grateful. After all, someone has to make sure your GPS gets you to the hospital in the shortest possible time when you inevitably collapse from boredom reading articles like this.
And that, ladies and gentlemen, is entirely my opinion.
