Dijkstra’s algorithm
What is the cheapest route when moves have different costs?
Always expands the cell that is cheapest to reach so far, so it finds the cheapest path even when steps cost different amounts.
Dijkstra’s algorithm records, for each cell, the cheapest cost found so far to reach it, and keeps the frontier in a priority queue ordered by that cost. It always expands the cheapest cell on the frontier.
When a cell is taken off the queue its cost is final: any other route to it would have to pass through a cell on the frontier that is at least as expensive. When the goal comes off the queue, its path is the cheapest, provided no cost is negative.
On a grid where a diagonal step costs about 1.41, this is where it differs from breadth-first search: it prefers the cheapest route over the one with the fewest steps. With no hint about where the goal is, it still spreads in a disc around the start.
Loading the demo…
The grid with Dijkstra selected. Turn diagonal moves on and off and watch the cheapest route change.
- 01Give the start a cost of 0 and every other cell infinity; put the start in a priority queue.
- 02Take the cell with the lowest cost.
- 03If it is the goal, follow the stored parents back to the start.
- 04For each neighbour, work out cost plus step cost. If that is lower than the neighbour’s recorded cost, record it, remember the parent and queue the neighbour.
- 05Repeat until the queue is empty.
function dijkstra(start, goal):
cost = {start: 0}
parent = {}
heap = [(0, start)]
while heap is not empty:
c, cell = heap.pop_min()
if c > cost[cell]: continue # an outdated entry
if cell == goal: return path_from(parent, goal)
for n, step in neighbours(cell):
new = c + step
if new < cost.get(n, infinity):
cost[n] = new
parent[n] = cell
heap.push((new, n))
return no_pathWith a binary heap as the priority queue. The log factor is the price of keeping the frontier ordered.
- Cheapest path, guaranteed, for any non-negative costs.
- Needs no heuristic.
- Gives the cheapest cost to every cell it expanded.
- Spreads in every direction, even away from the goal.
- Slower than A* whenever a good heuristic is available.
- Fails with negative costs.
- 01PathfindingThe reference for the cheapest path: A* with a good heuristic should find the same cost while expanding fewer cells.