Dijkstra’s algorithm was long thought to be the most efficient way to find a graph’s best routes. Researchers have now proved

Some variants of Dijkstra’s algorithm have seen real-world use in software like Google Maps. The new result probably won’t have such practical applications, for which there are many considerations beyond theoretical optimality guarantees. But it may change how researchers study optimality, prompting them to look beyond the usual worst-case analysis. Often, algorithms only achieve stronger guarantees at the cost of added complexity. The new result suggests that simple algorithms with these stronger guarantees might be more widespread than researchers previously thought — the team has already identified two other examples.