A New Algorithm Makes It Faster to Find the Shortest Paths

The original version of this story appeared in Quanta Magazine.

If you want to solve a tricky problem, it often helps to get organized. For example, you could divide the problem into several pieces and tackle the easier parts first. But this kind of sorting has a cost. You risk spending too much time putting the rooms in order.

This dilemma is particularly relevant to one of the most iconic problems in computing: finding the shortest path from a specific starting point in a network to any other point. It’s like an optimized version of a 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 are a wonderful problem that everyone can relate to,” said Mikkel Thorup, a computer scientist at the University of Copenhagen.

Intuitively, it should be easier 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 nearest point, then the nearest point, and so on. But to do this, you have to repeatedly determine which point is closer. You will sort the points by distance as you go. There is a fundamental speed limit for any algorithm that follows this approach: you cannot go 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 has designed a new algorithm that breaks it. It does not sort and runs faster than any algorithm that does.

“The authors were bold in thinking they could break this barrier,” said Robert Tarjan, a computer scientist at Princeton University. “It’s an incredible result.”

The frontier of knowledge

To mathematically analyze the shortest path problem, 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 it takes 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, the goal of an algorithm is to find the shortest path to all other nodes.

The most famous shortest path algorithm, designed by pioneering computer scientist Edsger Dijkstra in 1956, starts at the source and progresses step by step. This is an efficient 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 sort barrier sets a fundamental limit on how fast the algorithm can run.