A new algorithm makes finding shortest paths faster
The original version from This story appeared in Quanta Magazine.
If you’re trying to solve a complex problem, it often helps to be organized. For example, you might break the problem into pieces and solve the easiest parts first. But this kind of sorting comes at a cost. You may end up spending a lot of time sorting through the pieces.
This dilemma is particularly relevant to one of the most iconic problems in computer science: finding the shortest path from a particular starting point on a network to any other point. It’s like a version of the problem you have to solve every 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, finding the shortest route to nearby destinations should be easiest. So if you want to design the fastest possible algorithm for the shortest path problem, it makes sense to start by finding the closest point, then the closest point, and so on. But to do that, you have to find out over and over again which point is closer. You sort the points by distance. There is a fundamental speed limit to any algorithm that follows this method: you can’t go faster than it takes to sort.
Forty years ago, researchers designing shortest path algorithms encountered these “sorting barriers.” Now a team of researchers has developed a new algorithm that eliminates it. It is unordered and runs faster than any other algorithm.
“The authors were bold in thinking they could break this barrier,” said Robert Tarjan, a computer scientist at Princeton University. “This is an amazing result.”
The frontier of knowledge
To mathematically analyze the shortest problems, researchers use the language of graphs—grids of points or nodes connected by lines. Each link between nodes is labeled with a number called its weight, which can indicate the length of that segment or the time required to traverse it. Usually, there are many paths between any two nodes, and the shortest path is the path with the smallest sum of weights. Given a graph and a specific “source” node, the goal of an algorithm is to find the shortest path to every other node.
The most famous shortest path algorithm, invented by the pioneering computer scientist Edsger Dijkstra in 1956, starts at the source and works stepwise outward. This is an effective approach because knowing the shortest path to nearby nodes can help you find shortest paths to more distant nodes. But since the end result is a sorted list of shortest paths, the sorting constraint sets a fundamental limit on the algorithm’s execution speed.
