“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.”
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 an algorithm he’d devised in 2018 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.”
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.”
Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.
