Pathfinding
Dijkstra's Algorithm Visualiser
Always expand the cheapest cell found so far.
Dijkstra always expands the cheapest cell found so far, so crossing mud (cost 5) is put off until no cheaper route is left.
- Cells expanded
- 0
- In the open list
- 1
There are 303 cells to search on this board. The gap between that and the cells expanded is what a better search order buys you — walls and mud change it, so redraw the board and watch it move.
- Start
- End
- Wall
- Mud (costs 5)
- Waiting to be expanded
- Expanded
- Route
function dijkstra(grid, start, end) { const dist = new Map([[start, 0]]); const cameFrom = new Map([[start, null]]); const open = [start]; while (open.length > 0) { const cell = takeCheapest(open, dist); // cost so far if (cell === end) return path(cameFrom, end); for (const next of neighbours(grid, cell)) { const cost = dist.get(cell) + stepCost(grid, next); if (cost < (dist.get(next) ?? Infinity)) { dist.set(next, cost); cameFrom.set(next, cell); open.push(next); } } } return null; // the end is walled off}The highlighted line is the one that produced the picture on the left.
What Dijkstra's Algorithm does
Dijkstra's algorithm is breadth-first search for boards where steps cost different amounts. Instead of taking the cell that has been waiting longest, it takes the cell that is cheapest to reach. Because it always expands the cheapest option left, the first time it reaches a cell it has found the cheapest route to it.
How it works, step by step
- Give the start a cost of 0 and every other cell no cost yet.
- Take the unexpanded cell with the lowest cost so far.
- If it is the goal, stop: nothing cheaper is left to try, so this cost cannot be beaten.
- For each neighbour, work out the cost of reaching it through this cell. If that beats the best cost recorded for it, record the new cost and remember where it came from.
What to watch for
- The numbers in the cells are the cost to reach them, not the number of steps. Mud costs 5, open ground costs 1.
- The search goes round the mud rather than through it, while breadth-first search on the same board goes straight across. Both routes are correct answers to different questions.
- A cell's cost can be lowered after it has first been seen, when a cheaper way in turns up. It is only fixed once the cell is expanded.
- With every step costing 1, Dijkstra and BFS expand cells in the same order. Dijkstra is the general case; BFS is the special one.
Cost
| Time | O((cells + edges) log cells) |
|---|---|
| Extra space | O(cells) |
| Finds | Cheapest route |
| Handles costs | Yes, if never negative |
| Waiting list | Priority queue (cheapest first) |
When to reach for it
Whenever edges have different weights and none are negative: road networks with travel times, game maps with terrain, any network with latency on its links. With a negative weight the core assumption breaks and you need Bellman-Ford instead.