If you’ve been making the same commute for a long time, you’ve probably settled on what seems like the best route. But “best” is a slippery concept. Perhaps one day there’s an accident or road closure, and your fastest route becomes the slowest.

Scenarios like this are also a challenge for researchers who develop algorithms, the step-by-step procedures that computers use to solve problems. Many different algorithms can solve any given problem, and the question of which is best can be frustratingly ambiguous.

For example, imagine an algorithm that’s designed to find the fastest route between two points. There are lots of possible ways to design such an algorithm so that it doesn’t fail. A successful algorithm will always return the fastest route, whether you use it in London or Los Angeles, and whether it’s rush hour or the middle of the night.

But those algorithms aren’t all the same. The time each one takes to find the right answer will vary depending on where and when it’s used, and cases that are hard for one algorithm may be easy for another. Ideally, you’d want an algorithm that always runs faster than the others.

For most problems, it’s simply not possible to find such a unicorn. But a new proof shows that for the quintessential path-finding problem, one algorithm is close to ideal: Assuming worst-case traffic patterns, it’s the best approach on every possible street grid. What’s more, the algorithm is nearly 70 years old and a staple of the undergraduate computer science curriculum. The new work will be presented with a best-paper award at the 2024 Symposium on Foundations of Computer Science next week.