“It's a great algorithm,” said eric demaineA computer scientist at the Massachusetts Institute of Technology. “It's very fast, simple and easy to implement.”
To put this process into practice, you'll need to decide on a system for organizing your notes – a data structure in the language of computer science. This may seem like a minor technical detail, but the time spent searching your notes whenever you need to edit or delete an entry can have a big impact on the overall runtime of the algorithm.
Dijkstra's paper used a simple data structure that left room for improvement. Over the next decades, researchers developed better things, affectionately called “stacks”, in which some items are easier to find than others. They take advantage of the fact that Dijkstra's algorithm only needs to remove the entry for the nearest remaining vertex. “The heap is basically a data structure that allows you to do this very quickly,” said václav rozhonA researcher at the Institute for Computer Science, Artificial Intelligence and Technology (INSAIT) in Sofia, Bulgaria.
In 1984, two computer scientists developed a clever stack design which enabled Dijkstra's algorithm to reach a theoretical bound, or “lower bound”, on the time required to solve the single-source shortest-path problem. In a certain sense, this version of Dijkstra's algorithm is the best possible. This was the last word on the standard version of the problem for nearly 40 years. Things changed when some researchers took a closer look at what it meant to be “the best.”
best practice
Researchers typically compare algorithms by studying how they perform in the worst-case scenario. Imagine the world's most confusing road grid, then add some particularly confusing traffic patterns. If you insist on finding the fastest path in these extreme circumstances, the 1984 version of Dijkstra's algorithm is definitely unbeatable.
But hopefully your city doesn't have the worst road grid in the world. And so you might ask: is there any algorithm that is unbeatable on every road network? The first step to answer this question is to make the conservative assumption that each network has a worst-case traffic pattern. You then want your algorithm to find the fastest path through any possible graph layout, assuming the worst possible weights. Researchers call this condition “universal optimality.” If you have a universally optimal algorithm for the simple problem of getting from one point to another on a graph, it can help you beat rush hour traffic in every city in the world.