Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Pathfinding

Dijkstra's Algorithm Visualiser

Always expand the cheapest cell found so far.

Drawthen drag on the board
Board

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
O((cells + edges) log cells)extra space O(cells)

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

  1. Give the start a cost of 0 and every other cell no cost yet.
  2. Take the unexpanded cell with the lowest cost so far.
  3. If it is the goal, stop: nothing cheaper is left to try, so this cost cannot be beaten.
  4. 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

TimeO((cells + edges) log cells)
Extra spaceO(cells)
FindsCheapest route
Handles costsYes, if never negative
Waiting listPriority 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.

Read more