New Method Is the Fastest Way To Find the Best Routes:
If you want to solve a tricky problem, it often helps to get organized. You might, for example, break the problem into pieces and tackle the easiest pieces first. But this kind of sorting has a cost. You may end up spending too much time putting the pieces in order.
This dilemma is especially relevant to one of the most iconic problems in computer science: finding the shortest path from a specific starting point in a network to every other point. It's like a souped-up version of a problem you need to solve each time you move: learning the best route from your new home to work, the gym and the supermarket.
"Shortest-paths is a beautiful problem that anyone in the world can relate to," said Mikkel Thorup, a computer scientist at the University of Copenhagen.
Intuitively, it should be easiest to find the shortest path to nearby destinations. So if you want to design the fastest possible algorithm for the shortest-paths problem, it seems reasonable to start by finding the closest point, then the next-closest, and so on. But to do that, you need to repeatedly figure out which point is closest. You'll sort the points by distance as you go. 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.
Forty years ago, researchers designing shortest-paths algorithms ran up against this "sorting barrier." Now, a team of researchers has devised a new algorithm that breaks it. It doesn't sort, and it runs faster than any algorithm that does.
"The authors were audacious in thinking they could break this barrier," said Robert Tarjan, a computer scientist at Princeton University. "It's an amazing result."
To analyze the shortest-paths problem mathematically, researchers use 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.
The most famous shortest-paths algorithm, devised by the pioneering computer scientist Edsger Dijkstra 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 improved Dijkstra's original 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 certain assumptions about weights. Nobody knew how to extend their techniques to arbitrary weights. It seemed they'd hit the end of the road.
"The research stopped for a very long time," said Ran Duan, a computer scientist at Tsinghua University in Beijing. "Many people believed that there's no better way."
Duan wasn't one of them. 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.
Duan's interest in the sorting barrier dates back nearly 20 years to his time in graduate school at the University of Michigan, where his adviser was one of the researchers who worked out how to break the barrier in specific cases. But it wasn't until 2021 that Duan devised a more promising approach.
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. It decides where to go next by scanning this region's "frontier" — that is, all the nodes connected to its boundary. This doesn't take much time at first, but it gets slower as the algorithm progresses.
Duan instead 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.
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 a partial solution — 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.
"There could be a case that A can reach B very easily, but B cannot reach A very easily," said Xiao Mao, a computer science graduate student at Stanford University. "That's going to give you a lot of trouble."
In the summer of 2023, Mao 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."
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."
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.
Journal Reference:
Dijkstra, E. W.. A note on two problems in connexion with graphs, Numerische Mathematik (DOI: 10.1007/BF01386390)
(Score: 0) by Anonymous Coward on Thursday October 16, @03:18PM (10 children)
This sounds like a routing algorithm. And I guess it should. Routing very much is an undirected graph.
(Score: 2) by janrinok on Thursday October 16, @03:27PM (4 children)
It is frustrating. Although there is a link to the paper it is hidden behind a private paywall. If anyone has access to it can they are able to share the gist of it, I would appreciate it very much.
[nostyle RIP 06 May 2025]
(Score: 4, Informative) by Uncle_Al on Thursday October 16, @04:05PM (3 children)
https://ir.cwi.nl/pub/9256/9256D.pdf [ir.cwi.nl]
(Score: 2) by Uncle_Al on Thursday October 16, @04:07PM
They also got the year wrong. It was submitted in 1959 not 1956
(Score: 2) by janrinok on Thursday October 16, @04:09PM (1 child)
Thank you.
[nostyle RIP 06 May 2025]
(Score: 2) by Uncle_Al on Thursday October 16, @04:12PM
I also seem to remember this being talked about last year when the algorithm was first published.
(Score: 5, Insightful) by ledow on Thursday October 16, @05:54PM (4 children)
It's graph theory.
Graph theory as a discipline has myriad applications, you just don't realise them.
Routing - including networking and vehicular traffic - is the most obvious.
But it directly correlates to major problems in things like game theory, experimental logistics (i.e. how can we perform experiments with X variables to determine the maximum amount of outcomes with the minimum amount of trials? Used in everything from agriculture to medicine - e.g. testing several seeds, fertilizers and soils and determining their effects and the most effective combination in less than the obvious brute-force numbers of elongated multi-year trials), communications and even data recovery (graph theory is basically part of coding theory and vice versa - so your RAID arrays and your network checksums are doing things that have come from graph theory).
Like everything in maths - it clicks into everything else. And in this case, graph theory even has direct applications in computer science in many different areas.
(Score: 0) by Anonymous Coward on Thursday October 16, @11:27PM (2 children)
Do you know, is Design of Experiments based on graph theory, or is it coming from a different angle to address that problem?
(Score: 2) by sneftel on Friday October 17, @05:44AM
That’s a little like asking whether architecture is based on trigonometry. Yeah, kind of; obviously it’s an important source of tools; but it’s not really the “basis”. Graphs are important in analyzing causal and probabilistic connections.
(Score: 2) by ledow on Friday October 17, @07:30AM
Some of it is quite literally just graph theory.
My graph theory lecturer was paid handsome sums to design agricultural experiments - because they were able to look at the required information, look at the source experiments, cut them down to the bare minimum (saving millions) and then analyse the result to determine any interactions (good or bad) between the individual elements would could apply to design the next (again, severely reduct) round of experiments for the next year's crops.
And her part was entirely graph theory.
(Score: 0) by Anonymous Coward on Saturday October 18, @11:32PM
In the real world you don't necessarily need some academic solution that is provably better for all cases.
(Score: 5, Insightful) by OrugTor on Thursday October 16, @04:23PM (5 children)
I love reading this kind of article on SN. It epitomizes humanity's inner journey into the exercise of intellect - a vast region of unexplored knowledge. All we need to open it up is brilliance and persistence. Thank you Duan's team and thank you Janrinok for posting.
(Score: 2) by krishnoid on Thursday October 16, @05:40PM (4 children)
Not to mention that it keeps reminding us in the US that human knowledge *is* still moving forward.
(Score: 2) by ledow on Thursday October 16, @05:57PM (3 children)
And that AI has yet to make a single significant discovery of its own, even though this is just basic mathematics.
(Score: 2) by krishnoid on Thursday October 16, @06:07PM (2 children)
Maybe protein configurations [science.org] aren't significant enough, but it's still pretty important [nobelprize.org].
(Score: 4, Interesting) by HiThere on Friday October 17, @12:52AM
IIUC, those are projected protein configurations. There's an error rate.
This doesn't mean it's not significant, but it's something that needs to be checked rather than something that is true.
OTOH, I believe that AI has made a few math discoveries. (Not just a faster way to multiply two matrices of a specific size.) Whether the discoveries are "significant" is a matter of taste.
Javascript is what you use to allow unknown third parties to run software you have no idea about on your computer.
(Score: 4, Insightful) by ledow on Friday October 17, @07:19AM
It was told to find them.
And it's a large, fast, statistical model.
AI made no more "made the discovery" than, say, a lab assistant at a research lab instructed to spend years looking for a particular combination of these particular chemicals.
There's a reason why the human got the Nobel, and it's not to do with the committee's rules and regulations.