| Before driving to an unfamiliar destination, most of us plug the address into Google Maps, and the app spits out the best route in seconds. It does so by running a fast algorithm for an iconic math problem, called the shortest-path problem, which computer scientists have studied for nearly 70 years.
Algorithms for the shortest-path problem work with mathematical objects called graphs: networks of points connected by lines. These can represent road networks, communication networks, social networks and more. In a shortest-path problem, each link in the network is labeled with a number called its weight. For a road network, the weights might represent distance, travel time or the total cost of gas and tolls — whatever you want to cut down. In 1956, the pioneering computer scientist Edsger Dijkstra devised a simple algorithm that rapidly finds the shortest paths from a specific starting point to each other point in a graph. Other researchers later built on his work to make the algorithm even faster.
The shortest-path problem is just one of many classic computer science problems about navigating networks. Computer scientists have studied these problems since the early days of their field, and in the past few years, they've hit upon many breakthroughs.
What's New and Noteworthy
Dijkstra's algorithm for the shortest-path problem only works on graphs whose weights are all positive numbers. That's often a reasonable restriction, but some applications, like maximizing delivery revenue, require both positive and negative weights. The cost of a toll road, in this case, would be classed as a positive weight, whereas the profit from making a delivery would be a negative weight. This makes the problem much trickier, because the shortest path between two points can be very circuitous, involving lots of segments with positive weights and a segment with a large negative weight that cancels out most of the cost. However, researchers recently discovered that this added difficulty is actually an illusion. In 2023, I reported on a striking new algorithm that solves the shortest-path problem nearly as fast as theoretically possible, even when weights are negative.
In another surprising recent development, researchers found a way to improve Dijkstra's algorithm itself. Since the 1980s, researchers have known that it's the best possible shortest-path algorithm in a specific theoretical sense: It fares better than any other approach in a worst-case scenario. Last fall, I reported on a paper proving that if you just change the way Dijkstra's algorithm stores data, it becomes unbeatable in a much wider range of scenarios. "I can't imagine a more compelling research paper about a problem we teach students in undergrad algorithms," one researcher told me.
When you're trying to find the best route for a drive, it goes without saying that you can't take multiple paths at once. But that's not the case in all navigation problems. A freight company, for instance, might want to send a large fleet of trucks on a cross-country trip, but sending them all down the same route would clog up the road. To model this "minimum-cost flow" problem, computer scientists add another number to each link in a graph, representing its capacity limit. The minimum-cost flow problem seems harder than the shortest-path problem, because any algorithm must account for both the capacity and the length of each segment. But in 2022, Erica Klarreich reported on a new algorithm that solves the problem "absurdly fast" — essentially as fast as the best algorithms for the shortest-path problem.
Of course, algorithm researchers aren't always so lucky. One of the most famous navigation problems, called the traveling salesperson problem, asks for the shortest path that passes through every point in a graph — a much more daunting task than finding paths between pairs of points. All known algorithms for finding the perfect solution to the traveling salesperson problem are excruciatingly slow, making them impractical even for relatively small graphs. But computer scientists haven't given up. Since the 1970s, they've known how to rapidly find paths that are pretty good — not necessarily the shortest, but guaranteed to be at most 50% longer than the shortest (much shorter than most paths you might try). In 2020, Klarreich reported on another new algorithm that improved on that 50% figure — albeit by a tiny amount — for the first time in half a century.
All these results are great illustrations of how computer scientists continue to make new discoveries about age-old problems. Even after decades of study, they still haven't reached the end of the road. | 
