Pathfinding Algorithms — BFS, DFS, Dijkstra and A* (Interactive)

Navigation, game AI, maps, circuit routing, network topology — all reduce to the same problem: given a graph, find the best path from A to B. Four algorithms dominate the literature, and they make radically different trade-offs. This post puts them on the same grid so the differences are impossible to ignore.

The problem space

A grid is just a graph where each cell is a node and edges connect neighbours (4-directional here: up, down, left, right). Walls remove edges. The goal: find the shortest sequence of steps from the green cell to the red cell.

Two properties define what “best path” means and whether an algorithm can find it:

• Completeness — will it always find a path if one exists?
• Optimality — is the path it finds the shortest one?

These properties are not free. You pay for them with nodes explored.

BFS — Breadth-First Search

BFS explores nodes in layers: all nodes at distance 1, then all at distance 2, and so on. It uses a queue (FIFO) to maintain the frontier.

frontier = queue([start])
visited  = set([start])

while frontier is not empty:
    node = frontier.dequeue()
    if node == goal: return path
    for each neighbour of node:
        if neighbour not in visited:
            visited.add(neighbour)
            frontier.enqueue(neighbour)

Why it guarantees the shortest path: the first time BFS reaches the goal, it does so via the fewest edges — because it exhausted all shorter distances first.

The cost: on an open grid with no obstacles, BFS expands roughly a circle of radius d around the start. That circle’s area grows as πd². For large grids it explores a lot of territory it never needed to touch.

Properties: ✅ Complete · ✅ Optimal (unweighted) · ⚠️ Memory: O(V)

DFS — Depth-First Search

DFS plunges deep down one path before backtracking. It uses a stack (LIFO) — or recursion.

frontier = stack([start])
visited  = set()

while frontier is not empty:
    node = frontier.pop()
    if node in visited: continue
    visited.add(node)
    if node == goal: return path
    for each neighbour of node:
        if neighbour not in visited:
            frontier.push(neighbour)

Why it does not guarantee shortest path: DFS commits to the first direction it finds. If that direction happens to reach the goal via a long detour, it returns that path. There’s no mechanism to prefer short paths over long ones.

Where DFS is useful: cycle detection, topological sort, generating mazes (DFS with backtracking produces the classic recursive maze), connected components. Navigation is not its home territory.

Try it in the explorer above: clear the grid and watch DFS snake a single deep path while BFS fans out symmetrically.

Properties: ✅ Complete (finite graphs) · ❌ Not optimal · ✅ Memory: O(depth)

Dijkstra — Weighted shortest path

When edges have weights (costs), BFS breaks. A path with 3 expensive edges may cost more than a path with 10 cheap ones. Dijkstra handles this with a min-heap priority queue ordered by cumulative cost g.

heap = min_heap([(0, start)])
dist = {start: 0}

while heap is not empty:
    g, node = heap.pop_min()
    if node == goal: return path
    for (neighbour, weight) in edges(node):
        new_g = g + weight
        if new_g < dist.get(neighbour, ∞):
            dist[neighbour] = new_g
            heap.push((new_g, neighbour))

On a uniform grid (all edges cost 1), Dijkstra and BFS find the same shortest path. The exploration order may differ slightly (binary heaps don’t guarantee FIFO among equal-priority nodes), but the result is identical. The heap overhead makes Dijkstra slightly slower in this case — but on weighted graphs it’s the correct tool.

Key insight: Dijkstra always processes the cheapest-so-far node. This greedy choice is safe because edge weights are non-negative — a cheaper partial path can never become more expensive as you extend it.

Properties: ✅ Complete · ✅ Optimal (non-negative weights) · ⚠️ Memory: O(V + E) · Time: O((V + E) log V) with binary heap

A* — Informed search

A* extends Dijkstra with a heuristic function h(n) — an estimate of the remaining cost from node n to the goal. The priority queue is ordered by f = g + h instead of just g.

heap = min_heap([(h(start), start)])
g    = {start: 0}

while heap is not empty:
    f, node = heap.pop_min()
    if node == goal: return path
    for (neighbour, weight) in edges(node):
        new_g = g[node] + weight
        if new_g < g.get(neighbour, ∞):
            g[neighbour] = new_g
            f_score = new_g + h(neighbour)
            heap.push((f_score, neighbour))

The heuristic used here is Manhattan distance: |row_n - row_goal| + |col_n - col_goal|. It counts the minimum possible steps to the goal ignoring walls.

Admissibility: an admissible heuristic never overestimates the true remaining cost. Manhattan distance is admissible on a 4-directional grid because you can’t reach the goal in fewer steps than that distance. An admissible heuristic guarantees A* finds the optimal path.

Why it explores fewer nodes than Dijkstra: when two nodes have the same g cost, A* prefers the one that is geometrically closer to the goal. It doesn’t waste time exploring nodes that are cheap-so-far but heading in the wrong direction.

Properties: ✅ Complete · ✅ Optimal (admissible heuristic) · ✅ Efficient — fewest nodes for guaranteed optimality

What the comparison table tells you

Run the “Compare all” mode and look at the Nodes explored column for the same maze.

A* and BFS find the same path length. A* gets there by exploring a fraction of the nodes. On a 18×36 grid an open path, A* might explore 40 nodes while BFS explores 200. On larger grids with longer paths, the gap grows dramatically — this is why Google Maps doesn’t use BFS.

Choosing the right algorithm

The heuristic is the design decision

A*‘s quality depends entirely on h. A perfect heuristic (exact remaining cost) would navigate directly to the goal without exploring any extra nodes. An inadmissible heuristic (overestimates remaining cost) risks missing the optimal path — you get a faster algorithm that’s no longer guaranteed correct.

In practice, heuristic design is domain-specific:

• Grid navigation: Manhattan distance (no diagonals) or Euclidean distance (with diagonals)
• Road networks: straight-line distance between GPS coordinates
• Puzzle solving (15-puzzle): sum of Manhattan distances for all tiles
• Game AI: domain-specific cost estimates built from gameplay knowledge

The reason A* dominates game pathfinding, GPS routing and robotics isn’t that it’s complicated — it’s that the gap between “explores everything” and “explores just enough” matters enormously at real-world scale.