Dijkstra’s algorithm
Finds the cheapest way from a start to a goal. It always takes the cheapest place waiting in a priority queue, so costs spread out from the start like a flood.
- time O((V + E) log V)
- space O(V)
- uses a priority queue
What do these mean?
- Cost: what a move costs. On the maze, stepping onto ground costs 1, onto mud 3 and into water 9; on the graph, the number on the edge.
- Priority queue: a waiting line where the cheapest one goes first, not the one that came first.
- Estimate (h): a guess of the cost still to go. A* stays exact only if the guess is never too high.
- Relaxing an edge: checking whether going through the current place gives a neighbour a cheaper cost, and taking it if it does.
- in the queue
- current
- done
- cheapest way
- ground · 1
- mud · 3
- water · 9
- wall
New: Start at A1 with cost 0. It is the only one in the queue.
Space: play or pause. Left and right arrows: step. Home and End: jump.
Try this: Pick the marsh. The cheapest way goes all the way round the mud: twice as many moves as the straight line, yet cheaper (34 against 36).
How it works
Every place gets a cost: 0 for the start, infinity for the rest. Dijkstra keeps the places it has reached in a priority queue and always takes the cheapest one. That cost is then final, because any other way to it would have to pass through something at least as dear. From there it looks at each neighbour: if going through the place it just took is cheaper than the neighbour’s cost so far, the neighbour gets the new cost and remembers where it came from. When the goal is taken, following those links back gives the cheapest way.
When it is a good choice
Use Dijkstra when moves cost different amounts and none costs less than zero: road maps and satnavs, network routing, the cheapest chain of flights. When every move costs the same, BFS gives the same answer more simply. With negative costs Dijkstra can go wrong; Bellman–Ford handles those.