Dijkstra maze algorithm
Dijkstra's algorithm always expands the cell with the lowest distance from the start, so it finds the shortest path.
How it works
It keeps a priority queue keyed by distance from the start. Each step it takes the closest unfinished cell, marks it done, and updates its neighbours' distances. When the exit comes off the queue, its distance is final and the path is read back.
In a maze where every step costs the same, Dijkstra explores in exactly the same order as Breadth-First Search. It shines when steps have different costs. A* is Dijkstra with a heuristic added to point it at the goal.
What to watch for
Watch it flood outward in even rings, the same way BFS does. On a grid of equal steps they really are the same algorithm.
Properties
- Shortest path
- Always (non-negative costs)
- Finds the exit
- Always, if there is one
- Explores
- Like BFS on a maze
- Memory
- Priority queue
Race it
Same maze, same speed, first to the exit wins: Dijkstra vs A* Search. Or put it in a gauntlet, where the winner stays on.
FAQ
Is Dijkstra the same as BFS?
When every step costs the same, they visit cells in the same order. Dijkstra also handles different step costs; BFS doesn't.
Dijkstra or A*?
A* finds the same shortest path and usually explores fewer cells, as long as its heuristic never overestimates.