Key Points
If youve been making the same commute for a long time, youve probably settled on what seems like the best route..
But a new proof shows that for the quintessential path-finding problem, one algorithm is close to ideal: Assuming worst-case traffic patterns, its the best approach on every possible street grid..
In 1984, two computer scientists developed a clever heap design that enabled Dijkstras algorithm to reach a theoretical limit, or lower bound, on the time required to solve the single-source shortest-paths problem..
Those dreams came to fruition in 2021, when Haeupler and two graduate students proved that it was possible to build universally optimal algorithms for several important graph problems..
From left: Bernhard Haeupler, Vclav Rozho (top), Jakub Ttek (bottom), Robert Tarjan, and Richard Hladk proved that a version of Dijkstras algorithm is the best approach for every network layout...
