Scientists Establish the Best Algorithm for Traversing a Map

Edsger Dijkstra developed the classic algorithm for rapidly finding the shortest paths through a network in 1956 .

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 .

In 1984 , two computer scientists developed a clever heap design that enabled Dijkstra ’s algorithm to reach a theoretical limit, or “lower bound,” on the time required to solve the single-source shortest-paths problem.

That was the last word on the standard version of the problem for nearly 40 years .

Researchers call this condition “universal optimality” Bernhard Haeupler and two graduate students proved that it was possible to build universally optimal algorithms for several important graph problems.

Bernhard Haeupler , Václav Rozho , Jakub Ttek , Robert Tarjan , and Richard Hladík proved that a version of Dijkstra ’s algorithm is the best approach for every network layout.

The key ingredient turned out to be a special property of some data structures that lets them quickly access recently added items.

Heaps with this property were first constructed more than 20 years ago .