Graph search · Heuristics · A*

Pathfinding

BFS, Dijkstra, and A* race across the same grid. Watch the heuristic shape the search.

Three classic search algorithms run on one grid. BFS explores layer by layer; Dijkstra factors in weights; A* uses a heuristic — an informed guess at the remaining distance — to bias the search toward the goal. Drop walls, drop mud (cost 5), and load the maze preset to see how each algorithm trades exploration for guarantees.

BFS

Cells explored: 0
Path length: —
Path cost: —

Dijkstra

Cells explored: 0
Path length: —
Path cost: —

Cells explored: 0
Path length: —
Path cost: —

What’s happening under the hood

›BFS finds the shortest unweighted path. Optimal when every step costs the same. It does not understand mud — it counts steps, not cost.
›Dijkstra generalizes BFS to weighted graphs by pulling the lowest-cost frontier cell next. Optimal when edge costs are non-negative. Explores symmetrically because it has no sense of direction.
›A* keeps Dijkstra's optimality (when the heuristic never overestimates) but pulls the cell that minimizes cost-so-far + estimated-remaining. With Manhattan distance as the heuristic, exploration becomes goal-directed — fewer cells touched, same path quality.

Dig deeper

Phase 3 · Algorithms & Complexity

The concept you just explored is taught with full depth in the formal DURA curriculum.