Dijkstra (weighted grid)

O(E log V)

This is Dijkstra's shortest-path algorithm on a grid where each cell has an entry cost — ordinary cells cost 1, the tan "heavy" cells cost 5. It always expands the unvisited cell reachable most cheaply so far, settling cells in order of increasing total cost. Because cost, not step count, drives the choice, the cheapest path often bends around a patch of heavy terrain rather than ploughing straight through it — exactly where it differs from BFS, which only counts steps. With a min-priority queue it runs in O(E log V). Click to add walls; the heavy band is fixed so you can watch the route prefer the cheaper way around.

Click a cell to toggle a wall
Grid
Edit the input and press Play

How it works

  1. Give the start cost 0 and every other cell infinity.
  2. Expand the unvisited cell with the smallest cost so far.
  3. For each neighbour, the new cost is this cost plus the neighbour's entry cost.
  4. If that's cheaper, record it. The goal's final cost is the cheapest route — trace it back.

Pseudocode

1dijkstraGrid(grid, start, goal):     # O(E log V)2  dist[start] ← 0; rest ← ∞3  while cells remain:4    cell ← unvisited cell with least dist5    if cell = goal: stop6    for nbr in open neighbours(cell):7      nd ← dist[cell] + cost(nbr)      # cost = terrain weight8      if nd < dist[nbr]: dist[nbr] ← nd; prev[nbr] ← cell9  walk prev back — cheapest, not fewest steps