BFS, Dijkstra and A*: one weighted maze

The initial example

These are the results for the unchanged initial map. Editing the maze can change all three outcomes.

Same map, different selection rules

BFS removes cells from a FIFO queue and remembers the first route to each cell. It minimizes transitions, regardless of terrain. Its displayed cost is the sum along its chosen route, not a promise of minimum cost.

Dijkstra selects the smallest known cost g from the whole frontier. A* selects g + h. Both improve the distance and parent when they find a cheaper route. Movement follows open north/east/south/west passages. Equal priorities follow the order in which the current estimate was assigned; improving an estimate gives it a new queue order. The goal is tested when extracted, not when first discovered.

Entry costs are 1, 3 or 7. Pay for the next cell, including G; S is free. A passage works in both directions, but entering different terrain can cost differently. The editor changes costs and endpoints for all three searches together; walls stay fixed.

Why A* still finds minimum cost

Here h is Manhattan distance to G multiplied by the smallest cell cost on this map. It ignores walls and assumes every remaining move costs the minimum. This is a lower bound on the remaining cost.

Across a passage h can drop by at most one minimum-cost move, no more than the actual entry cost. This makes the heuristic consistent: a cell does not need reopening after extraction. Dijkstra and A* find minimum cost; their routes can differ when several are equally cheap. An estimate does not guarantee a reduction in work on every map.

With unit weights, a route’s cost equals its number of transitions. All three then optimize the same quantity, though A* may visit cells in a different order.

What one tick measures

An explored branch becomes thin and gray as soon as it has no pending descendants in the current parent tree. Its moving tip disappears when the segment finishes. A shared trunk stays colored while another branch still has work. Activity follows the queue and parent links at the current step.

One visual step groups the minimum-priority cells already waiting at its start: BFS by depth, Dijkstra by g, A* by g + h. All their segments grow together. Newly discovered or improved cells wait for later waves at their priority, even if A* gives them the current wave's priority. Their parent was therefore processed before the wave began: lines grow from connected branches, never from a different moving tip. The algorithms still extract cells sequentially internally, and stop immediately on extracting G, including partway through the last wave.

Thin lines show explored branches, bright tips show the current wave, and a brighter, thicker line shows a found route. A finished algorithm holds its result while the others continue. Terrain is neutral, and an unnumbered cell costs 1; colors belong to algorithms only. The three wave scales differ, so visual completion time and wave counts do not compare CPU speed.

Expanded counts extracted cells, including G. Route cost and transitions appear only once the goal is extracted. Frontier counts pending cells and excludes the extracted cell. The tick rate is a playback speed, not a CPU benchmark. Neighbor order, tie rules and heuristic affect the number of expansions.

Use the checkboxes above the map to show one or more traces without changing the computed comparison. Search lines can be hidden; waiting-cell dots can be enabled for unfinished searches. Above each trace, see the current depth or priority and the number of cells in its wave. Pause, move forward or back, seek or jump to the result. Manual stepping and seeking show complete waves; reduced-motion mode skips segment animation. Coordinates in the editor offer the same changes without clicking the canvas. Invalid coordinates preserve the current maze and search history.

This implementation

BFS uses a queue with a moving head: O(V+E) time. Dijkstra and A* scan an array for the minimum: O(V²+E), rather than a heap bound. Each algorithm uses O(V) working memory without the input graph. The comparison stores O(V) data after each of at most V extractions: O(V²) additional replay memory per algorithm. The immutable maze is shared by all three traces; the model limits comparisons to 256 cells.

The compact code below computes the result without replay snapshots. adjacency contains ordered {to, weight} lists; for the grid, each edge weight is the entry cost of its destination. For A*, pass the consistent scaled-Manhattan function used above (the default zero estimate reduces A* to Dijkstra).

JavaScript implementation

function search(adjacency, start, goal, method, heuristic = () => 0) {
  const n = adjacency.length;
  const valid = v => Number.isInteger(v) && v >= 0 && v < n;
  if (!["bfs", "dijkstra", "astar"].includes(method) || !valid(start) || !valid(goal))
    throw Error("Invalid search parameters");
  for (const neighbors of adjacency) for (const {to, weight} of neighbors)
    if (!valid(to) || !Number.isInteger(weight) || weight < 1 || weight > 9)
      throw Error("Expected entry costs from 1 to 9");
  const g = Array(n).fill(Infinity), parent = Array(n).fill(null);
  const priorityOrder = Array(n).fill(Infinity);
  const closed = Array(n).fill(false), open = [start];
  let head = 0, expanded = 0, order = 1;
  g[start] = 0;
  priorityOrder[start] = 0;
  const priority = v => g[v] + (method === "astar" ? heuristic(v) : 0);
  while (head < open.length) {
    let current;
    if (method === "bfs") current = open[head++];
    else {
      let best = 0;
      for (let i = 1; i < open.length; i++)
        if (priority(open[i]) < priority(open[best]) ||
            (priority(open[i]) === priority(open[best]) && priorityOrder[open[i]] < priorityOrder[open[best]])) best = i;
      current = open.splice(best, 1)[0];
    }
    expanded++; closed[current] = true;
    if (current === goal) {
      const path = [];
      for (let v = goal; v !== null; v = parent[v]) path.push(v);
      return { path: path.reverse(), cost: g[goal], expanded };
    }
    for (const {to, weight} of adjacency[current]) {
      if (closed[to]) continue;
      const unseen = !Number.isFinite(g[to]), candidate = g[current] + weight;
      if (method === "bfs" ? !unseen : candidate >= g[to]) continue;
      g[to] = candidate; parent[to] = current;
      priorityOrder[to] = order++;
      if (unseen) open.push(to);
    }
  }
  return null;
}