Home/Pathfinding/Dijkstra
Search algorithmsCTRL K

Dijkstra

· uniform cost · cheapest first
/pathfinding/dijkstra
EXPANDED
0
closed cells
OPEN SET
1
candidates in the heap
PUSHES
0
relaxations that improved g
COST
—
of the path once found
WALLS
28%
of 880 cells blocked
closedopencurrentpathstart / goalmud ×4
44×20 · 28% walls · seed 7 · 1079 steps
step 0 / 1078
Walls28
dijkstra.ts
1
function dijkstra(grid: Grid, start: Cell, goal: Cell) {
2
  const open = new MinHeap<Cell>([start]);
3
  const distance = new Map([[start, 0]]), parent = new Map();
4
  while (open.size > 0) {
5
    const current = open.pop(); // lowest distance
6
    if (current === goal) return rebuild(parent, current);
7
    for (const neighbor of neighbors(grid, current)) {
8
      const newDistance = distance.get(current)! + cost(grid, neighbor);
9
      if (newDistance < (distance.get(neighbor) ?? Infinity)) {
10
        distance.set(neighbor, newDistance); parent.set(neighbor, current);
11
        open.push(neighbor, newDistance);
12
      }
13
    }
14
  }
15
}
CURRENT STEP
line 2

Start at (3, 1), goal at (8, 42). The open set holds only the start.

// how it works

Understanding Dijkstra

Dijkstra · BFS that learned what things cost
01

The idea

Dijkstra's algorithm is breadth-first search with a price tag. Instead of a queue it keeps a priority queue ordered by g, the cheapest known cost to reach each cell, and always expands the cheapest open cell. When a neighbour can be reached more cheaply through the current cell, its cost and parent are updated.

On this grid the amber cells are mud and cost 4 instead of 1. BFS would walk straight through them, counting steps; Dijkstra routes around them when the detour is cheaper, and the first time it pops the goal the path is the cheapest one, not merely the shortest.

02

The four stages

1
popthe open cell with the lowest g
2
checkis it the goal? then rebuild
3
relaxcheaper neighbours get a new g
4
pathfollow parents back to start
03

Complexity

best
O(d log V)goal next to the start
average
O(E log V)with a binary heap
worst
O(E log V)the whole grid, like BFS
space
O(V)heap, costs and parents
04

Versus its siblings

PATH COST · 44×20 MAZE WITH MUD
dfs
190
greedy
96
bfs
78
a*
62
dijkstra
62
same maze · BFS's path is shorter in steps but walks through mud
05

Pseudocode

DIJKSTRA(start, goal)
  open ← {start}; dist[start] ← 0
  while open not empty
    current ← node in open with lowest dist
    if current = goal: return path via parent
    for each neighbour of current
      if dist[current] + cost(neighbour) < dist[neighbour]
        dist[neighbour] ← dist[current] + cost(neighbour); parent[neighbour] ← current; add neighbour to open
06

When to use

Weighted graphs with non-negative costs: road networks, network routing, terrain with different movement costs.
When you need the cheapest paths from one source to every node, not just to one goal: run it to exhaustion.
07

Pitfalls

Negative edges break it: a cell closed early might have been reachable more cheaply. Use Bellman–Ford.
With uniform costs it degenerates into BFS with a heap: slower, no better. Add a heuristic and it becomes A*.
Decreasing a key in the heap is awkward; pushing a duplicate and skipping stale pops is simpler and just as fast.
08

History

Edsger Dijkstra designed the algorithm in 1956 in about twenty minutes, at a café in Amsterdam, as a demonstration for the ARMAC computer: the shortest route between two Dutch cities. He published it in 1959 in a three-page paper. With Fibonacci heaps, Fredman and Tarjan brought it to O(E + V log V) in 1984.

Back to Pathfinding