Interactive demo
Dijkstra's Algorithm
Edsger W. Dijkstra published his algorithm in 1959. It always continues from the cheapest cell found so far, so its frontier grows by cost instead of by steps, and it is guaranteed to find the cheapest path.
Draw walls or mud on the grid and drag the start and the goal. Once a search is finished, every change is searched again right away. Paint a wide band of mud: the frontier slows down inside it, and the path goes around if that is cheaper. Every step into or out of mud costs more.
Playback
- Expanded
- –
- Frontier (max.)
- –
- Path cost
- –
Press Play or Next Step to start the search.
Grid
Options
Legend
- Start (drag to move)
- Goal (drag to move)
- Wall
- Mud
- Frontier (open list)
- Visited (closed list)
- Expanded right now
- Path
Properties
Optimal
Yes
Cells are finished in the order of their cost, so the goal is reached by the cheapest path.
Weighted cells
Yes
Handles any costs that are not negative, like the mud here.
Heuristic
No
No sense of direction: it searches as much away from the goal as towards it.
Any angle
No
Moves from cell to cell, straight or diagonally.
All pathfinding algorithms compared
| Algorithm | Optimal | Weighted cells | Heuristic | Any angle |
|---|---|---|---|---|
| Breadth-First Search | Without mud and diagonals | No | No | No |
| Depth-First Search | No | No | No | No |
| Dijkstra's Algorithm this page | Yes | Yes | No | No |
| Bidirectional Search | Yes | Yes | No | No |
| Greedy Best-First Search | No | No | Yes | No |
| A* Search | With weight 1 and an admissible heuristic | Yes | Yes | No |
| Jump Point Search | Without mud | No | Yes | No |
| Theta* | No | Shortcuts over open ground only | Yes | Yes |
1. A priority queue
- Give the start the cost 0 and every other cell an infinite cost.
- Take the cell with the lowest cost out of the priority queue. Its cost is now final.
- For every neighbor, check whether the way through this cell is cheaper than the best one known. If so, update its cost and parent.
- Repeat until the goal is taken out.
2. Costs of the steps
A step costs its length (1, or √2 diagonally) times the average weight of the two cells: 1 on open ground, 5 in mud. Dijkstra's algorithm works with any costs that are not negative.
3. Where it is used
Route planners, network routing protocols such as OSPF and many games use Dijkstra's algorithm or its descendants. It is also the base of A*, which adds an estimate of the remaining distance.
Credits
- Edsger W. Dijkstra: A note on two problems in connexion with graphs (Numerische Mathematik, 1959).