“It’s a great algorithm,” he said Erik Demainecomputer scientist at the Massachusetts Institute of Technology. “It’s very quick, simple and easy to implement.”
To put this procedure into practice, you need to choose a system for organizing your notes – a data structure, in computer science jargon. This may sound like a minor technical detail, but the time spent searching through your notes every time you need to edit or delete an entry can have a large impact on the overall algorithm run time.
Dijkstra’s paper used a elementary data structure that left room for improvement. Over the following decades, researchers developed better, affectionately called “stacks,” where certain items are easier to find than others. They exploit the fact that Dijkstra’s algorithm must always remove the entry for the nearest remaining vertex. “The heap is basically a data structure that allows you to do this very quickly,” he said Wacław Rozhonresearcher at the Institute of Informatics, Artificial Intelligence and Technology (INSAIT) in Sofia, Bulgaria.
In 1984, two computer scientists developed clever heap design this allowed Dijkstra’s algorithm to reach the theoretical limit, or “lower bound”, of the time required to solve the single-source shortest paths problem. In a sense, this version of Dijkstra’s algorithm is the best possible. This was the last word on the standard version of the problem for almost 40 years. Things only changed when several researchers took a closer look at what it meant to be “the best.”
Best behavior
Scientists typically compare algorithms by examining how they perform in worst-case scenarios. Imagine the most confusing street grid in the world, then add some particularly confusing traffic patterns. If you insist on finding the fastest routes in these extreme circumstances, the 1984 version of Dijkstra’s algorithm is probably unbeatable.
But let’s hope your city doesn’t have the worst street grid in the world. So you may ask: is there an algorithm that is unbeatable on every road network? The first step to answering this question is to make the conservative assumption that each network experiences worst-case traffic patterns. Then you want your algorithm to find the fastest paths in any possible graph layout, assuming the worst possible weights. Scientists call this condition “universal optimality.” If you had a universally optimal algorithm for solving the simpler problem of getting from one point on a graph to another, it could aid you beat rush hour traffic in every city in the world.