New algorithm makes finding shortest paths faster

The original version to This story Featured in Quanta Magazine.

If you want to solve a difficult problem, organization often helps. You could, for example, break the problem down into parts and tackle the easier parts first. But this type of sorting comes at a cost. You may end up spending a lot of time arranging the pieces.

This dilemma is particularly relevant to one of the most famous problems in computer science: finding the shortest path from a given starting point in the network to every other point. It’s like an upgraded version of a problem you need to solve every time you move: learning the best route from your new home to work, the gym, and the supermarket.

“Shortest path is a beautiful problem that anyone in the world can deal with,” he said. Mikel Thorupa computer scientist at the University of Copenhagen.

Intuitively, it is easier to find the shortest route to nearby destinations. So, if you want to design the fastest possible algorithm for the shortest path problem, it’s reasonable to start by finding the nearest point, then the next closest, and so on. But to do this, you have to repeatedly determine which point is closest. You’ll sort the points by distance as you go. There is a fundamental speed limit to any algorithm that follows this approach: you cannot move faster than the time it takes to sort.

Forty years ago, researchers designing shortest path algorithms ran into this sorting barrier. Now, a team of researchers has invented A new algorithm breaks it. It doesn’t sort, and it works faster than any algorithm that does.

“The authors were bold in thinking they could break down this barrier,” he said. Robert Tarjana computer scientist at Princeton University. “It’s an amazing result.”

Limits of knowledge

To analyze the shortest path problem mathematically, researchers use the language of graphs, which are 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 paths between any two nodes, and the shortest is the one whose weights sum 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 popular shortest path algorithms, I created Created by pioneering computer scientist Edsger Dijkstra in 1956, it starts at the source and works outward step by step. It is an effective approach, because knowing the shortest path to nearby nodes can help you find the shortest path to farthest nodes. But since the end result is an ordered list of shortest paths, the sorting barrier puts a fundamental limit on how fast the algorithm can run.