Computer Scientists Establish the Best Way to Traverse a Graph | Quanta Magazine

Edsger Dijkstra’s algorithm is nearly 70 years old and a staple of the undergraduate computer science curriculum.

The Dutch computer scientist developed the algorithm in 1956 .

It gives you an ordered list of travel times from your current location to every other point that you might want to visit.

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 became fascinated with the promise of universal optimality while writing a grant proposal in the mid-2010s .

Heaps with this property were first constructed over 20 years ago , but in all the years that followed, nobody made full use of it.

The new result suggests that simple algorithms with these stronger guarantees might be more widespread than previously thought.

Some variants of Dijkstra ’s algorithm have seen real-world use in software like Google Maps .