Graph Search, Frontier by Frontier

One scaffold, four algorithms

The four classic single-source shortest-path / reachability algorithms — BFS, DFS, Dijkstra, A* — share a single scaffold. Maintain a frontier of nodes you've discovered but not yet finalised. Pop one off, mark it finalised, add its neighbours to the frontier. Repeat until you reach the goal (or the frontier empties).

What changes between them? The data structure backing the frontier.

• BFS uses a FIFO queue → pops the shallowest node first → finds the shortest path on unweighted graphs.
• DFS uses a LIFO stack → pops the deepest node first → finds some path, not the shortest, but uses much less memory.
• Dijkstra uses a min-priority queue keyed on path cost so far → pops the cheapest-from-start node → optimal on weighted graphs with non-negative edges.
• A* uses a min-priority queue keyed on $f(n) = g(n) + h(n)$ (cost so far plus heuristic estimate to goal) → pops the most promising node → optimal whenever $h$ is admissible.

Different priority order, different behaviour, same underlying loop.

Draw, run, watch

Pick a tool, click cells to paint. Walls (black) block movement. Mud (brown) is passable but costs 5× a normal step — only Dijkstra and A* will care. Drag the green start or red goal anywhere. Then press run.

Things worth trying:

• Clear walls, run BFS and A* on the same empty grid. BFS explores a square-ish region of radius equal to the distance to goal. A* draws an oval pointed at the goal. Same shortest path, dramatically different work.
• Paint a long horizontal mud strip between start and goal. Run BFS — it counts every step the same, so it cuts straight through. Run Dijkstra — it routes around.
• Draw a C-shaped wall around the goal so the algorithm has to back-track. Run greedy best-first; it dives at the goal and only realises its mistake when blocked. A* recovers; greedy doesn't.
• Run DFS in an empty grid. It produces a wildly long path, then runs to the end and gives up. DFS is wrong for shortest-path problems and the demo makes it visible.

BFS — the unweighted shortest-path tool

Pop from a FIFO queue. Each pop either is the goal (return) or pushes its unvisited neighbours. Because the queue is FIFO, every node is popped at its shallowest discovery depth — the number of edges from the start.

BFS is optimal on unweighted graphs (or graphs with uniform edge weights) and runs in $O(V + E)$ time. It is not optimal once edges have different weights: BFS treats a mud cell the same as an empty one. That's the problem Dijkstra fixes.

DFS — depth-first, useful for the wrong reasons

Pop from a LIFO stack instead of a queue. You dive as deep as possible before backtracking. DFS is the wrong algorithm for shortest paths — but it's the right one for:

• Topological sort. Post-order DFS on a DAG gives you a reverse topological ordering.
• Cycle detection. A back-edge during DFS = cycle.
• Connected components. Each top-level DFS call paints one component.
• Memory. DFS uses $O(\text{depth})$ memory; BFS uses $O(\text{frontier width})$. On wide, shallow graphs, DFS dominates.
• Articulation points / bridges. Tarjan's algorithm extracts both from a single DFS pass.

The grid demo above does shortest path, which is the wrong job for DFS — try it and observe the absurd path it finds.

Dijkstra — BFS with a priority queue

Replace BFS's FIFO queue with a min-priority queue keyed on the current best-known cost from start. Pop the node with the smallest cost. The first time you pop a node, you have its final shortest-path cost. Update neighbours by relaxation:

With a binary heap (see the trees article) Dijkstra runs in $O((V + E) \log V)$. With a Fibonacci heap, $O(V \log V + E)$, because the decrease-key operation becomes $O(1)$ amortised.

A* — Dijkstra with a hint

Dijkstra has no notion of where the goal is. A* fixes that: change the priority key from "cost from start" to "estimated total cost through this node":

where $g(n)$ is the actual cost from start to $n$ and $h(n)$ is a heuristic estimate of the remaining cost from $n$ to goal. Three regimes:

• $h \equiv 0$. A* reduces exactly to Dijkstra. Slow, optimal.
• $h$ exactly equals the true remaining cost. A* expands only the nodes on the shortest path. Optimal, fastest possible.
• $h$ is anywhere between. A* expands roughly the band of nodes whose $f$-score is at most the optimum. Tighter $h$ means tighter band.

For correctness we need $h$ to be admissible — it must never overestimate the true remaining cost. On a 4-connected grid with uniform-cost steps, the Manhattan distance is admissible. On an 8-connected (diagonal) grid, use Chebyshev or octile distance. Euclidean distance is admissible everywhere but loose on grid graphs.

For A* to never re-expand a node we also want $h$ to be consistent (a.k.a. monotone): $h(n) \le c(n, n') + h(n')$ for every edge $(n, n')$. Most "obvious" heuristics on grids — Manhattan, Euclidean — are consistent.

Greedy best-first — the cautionary tale

What if you priority-order on just $h(n)$, ignoring the cost paid so far? That's greedy best-first search. It feels like A* with the $g$-term dropped, and it can find a path very quickly on easy maps. But the moment a wall sits between the greedy direction and the goal, it dives into a dead end and slogs back out.

Greedy best-first is not optimal. It produces some path, which may be far from shortest. Useful when (a) you trust the heuristic, (b) you want speed over optimality, and (c) you can re-plan if the path is bad. Otherwise: A*.

Try the C-shaped wall trap above with greedy best-first; watch it bounce off the wall before recovering.

The cheat sheet

Sharp edges

• BFS is iterative deepening's friend, not its replacement. If your graph is infinite (or effectively so), BFS will blow memory on the frontier before it finishes. Iterative deepening DFS (IDDFS) keeps DFS's $O(\text{depth})$ memory while still finding shortest paths.
• A* re-expansion. With a heuristic that is admissible but not consistent, a node can be re-added to the frontier with a better $g$. Handle this by checking if the popped node's $g$ matches the recorded best; if not, skip.
• Tie-breaking in A* matters. Two nodes with equal $f$ can be popped in different orders, and the order changes which path A* returns. Standard trick: break ties by preferring the larger $g$ (closer to goal). This often shrinks the explored set dramatically.
• Bidirectional search. Run BFS / A* from start and goal simultaneously; stop when the frontiers meet. Squares the work in the best case ($O(b^{d/2})$ instead of $O(b^d)$ for branching factor $b$ and depth $d$).
• Jump-point search. On uniform-cost grids, you can skip whole runs of cells when nothing interesting changes. Order-of-magnitude speed-up over A* for game maps.
• D* and LPA*. When the graph is changing (obstacles appear, edges close), replanning from scratch is wasteful. D* Lite reuses information from the previous run; the canonical algorithm behind Mars-rover path planners.

Reading list

• Dijkstra, 1959 — A note on two problems in connexion with graphs. Two pages. Stays the algorithm of choice for sixty-plus years.
• Hart, Nilsson, Raphael, 1968 — A Formal Basis for the Heuristic Determination of Minimum Cost Paths. The original A* paper.
• Pearl, 1984 — Heuristics: Intelligent Search Strategies for Computer Problem Solving. The definitive treatment of admissibility, consistency, and the A* family.
• Koenig & Likhachev, 2002 — D* Lite. Incremental replanning for dynamic graphs.
• Harabor & Grastien, 2011 — Online Graph Pruning for Pathfinding on Grid Maps. Jump-point search; A* on grids without the wasted work.
• Sturtevant's Moving AI repository — standard benchmark maps for pathfinding research, including the Baldur's Gate II and StarCraft maps.