Grid Dijkstra (weighted cells)

Dijkstra on a grid where each cell has its own entry cost (digit 1–9). Finds the lowest-total-cost path from S to E. '.' cells cost 1, walls '#' are blocked.

time O(rows × cols × log(rows × cols))

space O(rows × cols)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

dist[start] = 0; others = ∞
pq = min-heap
while pq:
  (d, r, c) = pop-min
  for (dr, dc) in 4-neighbours:
    nd = d + cost(nr, nc)
    if nd < dist[nr][nc]:
      dist[nr][nc] = nd
      pq.push((nd, nr, nc))