Dijkstra's Algorithm

Spotting one

Something travels out from a starting point and you want the cheapest, shortest or fastest way to reach somewhere else. Every step has a cost and no cost is negative.

Cost is doing a lot of work in that sentence. It is often time, money, distance or risk.

Do you even need it?

If every step costs the same, you do not. Plain breadth-first search is simpler and quicker.

If any step can cost a negative amount, Dijkstra is wrong and will hand you a confident wrong answer. Use Bellman-Ford.

Where to start

Network Delay Time. Ordinary network, ordinary costs, and the question is just how long until the last point hears the signal.

Then Path with Minimum Effort, which quietly changes the rules. The cost of a route is not the sum of its steps, it is the single worst step in it. The method does not change at all. Only what you mean by cost so far changes, and once that clicks a whole family of problems opens up.

Path with Maximum Probability changes them again: costs multiply instead of adding, and you want the biggest result rather than the smallest.

Number of Ways to Arrive at Destination asks you to count cheapest routes as well as find one. Swim in Rising Water is the hardest here and puts the worst step idea on a grid.

Common mistakes

Using it when a cost can be negative. Easily the most common misuse.

Finalising a point and then updating it again later. Once Dijkstra settles a point it is settled, and reprocessing it means something else is wrong.

Scanning the whole list each round to find the nearest unvisited point. It works. It is also what makes a fast method slow. The priority queue is the point.