Dijkstra (Grid)

Graphs

avgO((V + E) log V)worstO((V + E) log V)spaceO(V)

Start at (7, 2) with distance 0; every other cell is unknown (∞)

1 / 406

Code

function dijkstra(grid: Grid, start: number, end: number) {  const dist = new Map([[start, 0]]);  const prev = new Map<number, number>();  const done = new Set<number>();  const open = new PriorityQueue<number>(); // pops the smallest distance first  open.push(start, 0);  while (open.size > 0) {    const cell = open.pop()!;    if (done.has(cell)) continue; // stale: a cheaper copy was already popped    done.add(cell);    if (cell === end) return { cost: dist.get(end)!, path: buildPath(prev, end) };    for (const next of grid.neighbours(cell)) {      if (grid.isWall(next) || done.has(next)) continue;      const alt = dist.get(cell)! + grid.cost(next);      if (alt < (dist.get(next) ?? Infinity)) {        dist.set(next, alt);        prev.set(next, cell);        open.push(next, alt);      }    }  }  return { cost: Infinity, path: [] };}function buildPath(prev: Map<number, number>, end: number) {  const path = [end];  while (prev.has(path[0])) path.unshift(prev.get(path[0])!);  return path;}

procedure Dijkstra(grid, start, end)  dist ← {start: 0}  prev ← empty map  done ← ∅  open ← min-priority queue  insert start into open with priority 0  while open is not empty do    cell ← extract-min(open)    if cell ∈ done then skip it    add cell to done    ▷ dist[cell] is now final    if cell = end then return dist[end], buildPath(prev, end)    for each neighbour next of cell (up, right, down, left) do      if next is a wall or next ∈ done then skip it      alt ← dist[cell] + cost(next)      if alt < dist[next] (∞ if unset) then        dist[next] ← alt        prev[next] ← cell        insert next into open with priority alt      end if    end for  end while  return ∞, no pathend procedureprocedure buildPath(prev, end)  path ← [end]  while prev[first of path] exists do prepend it to path  return pathend procedure

Variables

open=1

Counters

visited: 0
relaxations: 0

Draw

Size

Drag on the grid to draw. Grab the start or end cell to move it. Edits re-run the search from step 1.

How it works

Dijkstra's algorithm always expands the open cell with the smallest known distance, so on a weighted grid it finds the cheapest path rather than the one with fewest moves. Entering a cell costs its weight (the mud patches here cost 5), and the optimal route detours around them when that is cheaper.

Complexity

Best: O(1)
Average: O((V + E) log V)
Worst: O((V + E) log V)
Space: O(V)

Dijkstra (Grid)

How it works

Complexity

Search algorithms