Original version With this story appeared in Quanta Magazine.
If you want to solve a arduous problem, it often helps to be organized. For example, you can divide the problem into parts and tackle the easiest parts first. But this kind of sorting comes at a cost. You may find that you spend too much time putting things in the right order.
This dilemma is particularly relevant in the case of one of the most characteristic problems of computer science: finding the shortest path from a given starting point in a network to any other point. It’s like a refreshed version of the problem you have to solve every time you move: knowing the best route from your recent house to work, to the gym and to the supermarket.
“Shortest paths are a beautiful problem that everyone in the world can identify with,” he said Mikkel Thorupcomputer scientist at the University of Copenhagen.
Intuitively, it will be easiest to find the shortest route to nearby destinations. So if you want to design the fastest possible algorithm for a shortest path problem, it seems reasonable to start by finding the closest point, then the closest one, and so on. But to do this, you need to repeatedly determine which point is closest. As time goes by you will sort the points by distance. There is a fundamental speed limit to any algorithm using this approach: it cannot run faster than the time it takes to sort.
Forty years ago, researchers designing shortest path algorithms encountered this “sorting barrier.” Now a team of researchers have come up with it a new algorithm that breaks it. It doesn’t sort and runs faster than any algorithm that does.
“The authors were brave to think they could break this barrier,” he said Robert Tarjancomputer scientist at Princeton University. “It’s an amazing result.”
The frontier of knowledge
To mathematically analyze the shortest path problem, researchers employ the language of graphs – networks of points or nodes connected by lines. Each connection between nodes is marked with a number called its weight, which can represent the length of that section or the time it takes to travel it. Typically, there are multiple 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, the goal of the algorithm is to find the shortest path to every other node.
The the most famous shortest path algorithm, made up by pioneering computer scientist Edsger Dijkstra in 1956, it starts at the source and works outward step by step. This is an effective approach because knowing the shortest path to nearby nodes can facilitate find the shortest path to more distant ones. However, since the end result is a sorted list of shortest paths, the sorting barrier places a fundamental limit on the speed of the algorithm.