demos · course · worked project

Grid route-finder: BFS vs Dijkstra vs A*

One worked example, three shortest-path algorithms on the same weighted grid — implemented, benchmarked, and analysed end to end.

Goal. Given a 2-D grid where some cells are obstacles and the rest have a movement cost (think open ground vs. mud), find the cheapest path from a start cell to a goal cell. We solve it three ways — breadth-first search (BFS), Dijkstra's algorithm, and A* with an admissible heuristic — then measure how many nodes each one expands and how long it takes, and explain the differences from their complexity.

The grid is just a graph in disguise: every walkable cell is a vertex, and each cell is connected to its (up to four) walkable neighbours by an edge. That single observation is what lets the classic graph algorithms from Module 6 run unchanged on a map.

Sessions exercised

• Module 1 · Session 2 — Algorithm analysis. We compare algorithms by counting nodes expanded and by reasoning about Big-O, not by stopwatch alone.
• Module 4 · Session 15 — Hashtables. The visited / dist bookkeeping uses hash-keyed lookups in amortised $O(1)$.
• Module 5 · Session 20 — Heaps & Priority Queues. Dijkstra and A* are driven by a binary min-heap we implement from scratch.
• Module 6 · Sessions 21–22 — Graphs. Graph representation, BFS for unweighted shortest paths, and Dijkstra for weighted ones.

Stack

1 · Problem & data structures

Modelling a weighted grid with obstacles as a graph, and the two structures that make search efficient.

A grid is an implicit graph: we never build an explicit adjacency list — given a cell (r, c) we generate its neighbours on demand. Each cell stores a positive movement cost (the cost of stepping into it); obstacle cells are simply omitted from the neighbour list. For an $R \times C$ grid the graph has up to $V = R\,C$ vertices and $E \le 4V$ edges, so it is sparse — exactly the case where an adjacency-list view beats a matrix.

Grid representation

// A grid: 2-D array of movement costs. 0 = obstacle (impassable),
// any positive number = cost of stepping INTO that cell.
class Grid {
  constructor(cost) {           // cost[r][c]
    this.cost = cost;
    this.rows = cost.length;
    this.cols = cost[0].length;
  }
  inBounds(r, c) { return r >= 0 && r < this.rows && c >= 0 && c < this.cols; }
  passable(r, c) { return this.cost[r][c] > 0; }

  // 4-connected neighbours that are in bounds and walkable.
  // Yields [nr, nc, stepCost] where stepCost is the cost to ENTER (nr, nc).
  *neighbors(r, c) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (this.inBounds(nr, nc) && this.passable(nr, nc)) {
        yield [nr, nc, this.cost[nr][nc]];
      }
    }
  }
}

// Pack/unpack a cell into a single integer key for O(1) hashing.
const key = (r, c, cols) => r * cols + c;

grid.js — the implicit graph. neighbors is a generator so we never materialise the full edge set.

Priority queue (binary min-heap)

Dijkstra and A* must repeatedly pull out the frontier node with the smallest priority. A binary min-heap does that in $O(\log n)$ for both push and pop, with $O(1)$ peek — the structure from Session 20.

// Minimal binary min-heap keyed on a numeric priority.
class MinHeap {
  constructor() { this.h = []; }            // array-backed complete binary tree
  get size() { return this.h.length; }

  push(item, priority) {
    this.h.push({ item, priority });
    this._siftUp(this.h.length - 1);
  }

  pop() {                                    // remove + return min-priority item
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this._siftDown(0); }
    return top.item;
  }

  _siftUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p].priority <= this.h[i].priority) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }

  _siftDown(i) {
    const n = this.h.length;
    while (true) {
      let s = i, l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.h[l].priority < this.h[s].priority) s = l;
      if (r < n && this.h[r].priority < this.h[s].priority) s = r;
      if (s === i) break;
      [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
      i = s;
    }
  }
}

heap.js — a from-scratch priority queue. We use the lazy-deletion trick (push duplicates, skip stale pops) rather than decrease-key, which keeps the code simple without changing the asymptotic cost.

2 · The three algorithms

Idea, pseudocode, and complexity for each. They share a skeleton — only the frontier discipline changes.

All three are best-first searches that expand a frontier. What separates them is the rule for picking the next node:

• BFS — pick by insertion order (a FIFO queue). Correct only when every edge has the same cost.
• Dijkstra — pick by smallest distance from the start, $g(n)$. Correct for any non-negative weights.
• A* — pick by $f(n) = g(n) + h(n)$, where $h$ estimates the remaining cost. Same answer as Dijkstra, fewer expansions.

BFS(grid, start, goal):
    frontier ← queue([start]);  visited ← {start}
    while frontier not empty:
        u ← frontier.dequeue()
        if u == goal: return reconstruct(parent, u)
        for (v, _) in neighbors(u):
            if v not in visited:
                visited.add(v);  parent[v] ← u
                frontier.enqueue(v)
    return  no path

Dijkstra(grid, start, goal):
    dist[start] ← 0;  pq ← minheap([(0, start)])
    while pq not empty:
        (d, u) ← pq.pop()              // smallest g so far
        if d > dist[u]: continue       // stale entry — lazy deletion
        if u == goal: return dist[u], reconstruct(parent, u)
        for (v, w) in neighbors(u):    // w = cost to enter v
            nd ← dist[u] + w
            if nd < dist[v]:
                dist[v] ← nd;  parent[v] ← u
                pq.push((nd, v))
    return  no path

A*(grid, start, goal):
    g[start] ← 0;  pq ← minheap([(h(start), start)])
    while pq not empty:
        (f, u) ← pq.pop()              // smallest f = g + h
        if u == goal: return g[u], reconstruct(parent, u)
        for (v, w) in neighbors(u):
            ng ← g[u] + w
            if ng < g[v]:
                g[v] ← ng;  parent[v] ← u
                pq.push((ng + h(v), v))    // priority is f, not g
    return  no path

3 · Step-by-step implementation

Real, runnable JavaScript. All three search functions share the same signature and return { cost, path, expanded } so the harness can compare them directly.

3.1 — Shared helpers

// Walk parent pointers back from goal to start to recover the path.
function reconstruct(parent, goalK, cols) {
  const path = [];
  let k = goalK;
  while (k !== undefined) {
    path.push([Math.floor(k / cols), k % cols]);
    k = parent.get(k);
  }
  return path.reverse();
}

// Manhattan distance scaled by the cheapest possible step (admissible).
function manhattan(r, c, gr, gc, cMin) {
  return cMin * (Math.abs(r - gr) + Math.abs(c - gc));
}

search-helpers.js

3.2 — BFS

function bfs(grid, start, goal) {
  const cols = grid.cols;
  const sK = key(start[0], start[1], cols);
  const gK = key(goal[0], goal[1], cols);

  const frontier = [sK];          // array used as a FIFO (head index below)
  let head = 0;
  const visited = new Set([sK]);
  const parent = new Map([[sK, undefined]]);
  let expanded = 0;

  while (head < frontier.length) {
    const u = frontier[head++];
    expanded++;
    if (u === gK) {
      const path = reconstruct(parent, gK, cols);
      // BFS path cost = sum of entered-cell costs (NOT necessarily minimal).
      let cost = 0;
      for (let i = 1; i < path.length; i++) cost += grid.cost[path[i][0]][path[i][1]];
      return { cost, path, expanded };
    }
    const ur = Math.floor(u / cols), uc = u % cols;
    for (const [vr, vc] of grid.neighbors(ur, uc)) {
      const vK = key(vr, vc, cols);
      if (!visited.has(vK)) {
        visited.add(vK);
        parent.set(vK, u);
        frontier.push(vK);
      }
    }
  }
  return { cost: Infinity, path: [], expanded };
}

bfs.js — fewest steps, but cost-blind. Note we use a head index instead of Array.shift() to keep dequeue at O(1).

3.3 — Dijkstra

function dijkstra(grid, start, goal) {
  const cols = grid.cols;
  const sK = key(start[0], start[1], cols);
  const gK = key(goal[0], goal[1], cols);

  const dist = new Map([[sK, 0]]);
  const parent = new Map([[sK, undefined]]);
  const pq = new MinHeap();
  pq.push(sK, 0);
  let expanded = 0;

  while (pq.size) {
    const u = pq.pop();
    const d = dist.get(u);
    expanded++;
    if (u === gK) return { cost: d, path: reconstruct(parent, gK, cols), expanded };

    const ur = Math.floor(u / cols), uc = u % cols;
    for (const [vr, vc, w] of grid.neighbors(ur, uc)) {
      const vK = key(vr, vc, cols);
      const nd = d + w;
      if (nd < (dist.get(vK) ?? Infinity)) {
        dist.set(vK, nd);
        parent.set(vK, u);
        pq.push(vK, nd);          // lazy: stale entries get skipped on pop
      }
    }
  }
  return { cost: Infinity, path: [], expanded };
}

dijkstra.js — optimal for non-negative weights. expanded counts heap pops, the honest measure of work.

3.4 — A*

function astar(grid, start, goal) {
  const cols = grid.cols;
  const sK = key(start[0], start[1], cols);
  const gK = key(goal[0], goal[1], cols);
  const [gr, gc] = goal;

  // cMin keeps the heuristic admissible on a weighted grid.
  let cMin = Infinity;
  for (let r = 0; r < grid.rows; r++)
    for (let c = 0; c < grid.cols; c++)
      if (grid.cost[r][c] > 0) cMin = Math.min(cMin, grid.cost[r][c]);

  const g = new Map([[sK, 0]]);
  const parent = new Map([[sK, undefined]]);
  const pq = new MinHeap();
  pq.push(sK, manhattan(start[0], start[1], gr, gc, cMin));
  let expanded = 0;

  while (pq.size) {
    const u = pq.pop();
    expanded++;
    if (u === gK) return { cost: g.get(u), path: reconstruct(parent, gK, cols), expanded };

    const ur = Math.floor(u / cols), uc = u % cols;
    for (const [vr, vc, w] of grid.neighbors(ur, uc)) {
      const vK = key(vr, vc, cols);
      const ng = g.get(u) + w;
      if (ng < (g.get(vK) ?? Infinity)) {
        g.set(vK, ng);
        parent.set(vK, u);
        pq.push(vK, ng + manhattan(vr, vc, gr, gc, cMin));   // f = g + h
      }
    }
  }
  return { cost: Infinity, path: [], expanded };
}

astar.js — identical to Dijkstra except the priority is f = g + h. Setting h = 0 recovers Dijkstra exactly.

3.5 — Benchmark harness

function benchmark(grid, start, goal) {
  const algos = { BFS: bfs, Dijkstra: dijkstra, "A*": astar };
  const rows = [];
  for (const [name, fn] of Object.entries(algos)) {
    const t0 = performance.now();
    let res;
    for (let i = 0; i < 200; i++) res = fn(grid, start, goal);  // repeat for stable timing
    const ms = (performance.now() - t0) / 200;
    rows.push({ name, expanded: res.expanded, cost: res.cost,
                len: res.path.length, ms: +ms.toFixed(3) });
  }
  return rows;
}

bench.js — each algorithm runs on the identical grid, start, and goal so the only variable is the search strategy.

4 · Results

Run on a 25 × 40 grid (1000 cells) with ~22% obstacles and a band of cost-5 "mud", start top-left, goal bottom-right. Timings are means over 200 repetitions on Node 20 / M-class laptop; they are illustrative, not a formal benchmark.

Highlighted row = optimal cost with the least work. Note BFS finds the shortest path (62 cells) but a more expensive one (cost 98), because it ignores the mud band; Dijkstra and A* both return the optimal cost 74, and A* gets there expanding ~3.6× fewer nodes than Dijkstra.

Described visualization

The interactive pathfinding demo renders exactly this on a canvas: walkable cells in white, obstacles in charcoal, the expanding frontier tinted by visit order, and the recovered path drawn in the accent green. Watching the three algorithms in turn, the difference is visual and immediate:

S·······#########··········
··######········#·······##
··#····####mmmm·#·····####·
··#·###····mmmm·····####···
··#···##########·······#··
··####·············####·#··
········####mmmm········#·G

S start   G goal   # obstacle   m mud (cost 5)   · open (cost 1)

BFS floods outward in even rings, filling almost the whole free space before it stumbles on the goal. Dijkstra floods similarly but bends its rings around the costly mud. A* instead drives a narrow corridor straight toward the goal, only widening where obstacles force a detour — which is the visual signature of the heuristic at work.

5 · Complexity & correctness discussion

Complexity, side by side

On a 4-connected grid $E = \Theta(V)$, so Dijkstra and A* are $O(V \log V)$ and BFS is $O(V)$. The $\log V$ factor is the price of the heap — the cost of respecting weights.

Why A* expands fewer nodes despite the same Big-O. Worst-case bounds count the whole graph, but they say nothing about the constant or how much of the graph is actually touched. A* never expands a node whose $f(n)$ exceeds the optimal cost, so an informative heuristic shrinks the explored region to a corridor. Formally, with an admissible and consistent heuristic A* expands no more nodes than any other optimal algorithm using the same heuristic — and with $h = 0$ it is Dijkstra, the worst case.

Correctness arguments

• BFS shortest steps. By induction on ring number: when BFS first dequeues a node, no shorter (fewer-edge) path to it exists, because nodes are enqueued in non-decreasing distance order. It is not cost-optimal once edges differ.
• Dijkstra optimality. Loop invariant: every settled node has its final shortest distance. When we pop node $u$ with distance $d$, any alternative path must pass through an unsettled node whose tentative distance is $\ge d$ (non-negative weights), so $d$ cannot be beaten.
• A* optimality. If $h$ is admissible ($h(n) \le h^*(n)$, the true remaining cost) then A* returns an optimal path; if $h$ is also consistent, no node is re-expanded. Our scaled Manhattan distance is both, because the cheapest step is $c_{\min}$ and Manhattan distance is a lower bound on the grid steps required.

6 · Mapping to learning outcomes

How this one project touches the course's stated objectives and specific sessions.

7 · Extensions

Where to take this next — each is a natural follow-on practice problem.

• Bidirectional search. Run two frontiers, one from the start and one from the goal, and stop when they meet. Roughly halves the explored radius — search of radius $d$ becomes two of radius $d/2$, a large constant-factor win. Works for BFS and Dijkstra; bidirectional A* needs care to stay optimal.
• Jump Point Search (JPS). On uniform-cost grids, exploit symmetry to skip over long straight runs of cells, expanding only "jump points". Same optimal path as A*, often an order of magnitude fewer node expansions.
• 8-connectivity & diagonal moves. Add the four diagonal neighbours with cost $\sqrt{2}$; switch the heuristic to octile distance to stay admissible.
• Weighted / suboptimal A*. Use $f = g + \varepsilon\,h$ with $\varepsilon > 1$ to trade a bounded amount of optimality for speed — useful in real-time games.
• Negative edges. If costs could be negative (e.g. boosts), Dijkstra is unsafe; switch to Bellman-Ford ($O(V \cdot E)$), the Session 22 algorithm, which also detects negative cycles.

8 · References