BFS, Dijkstra and A*: What Three Pathfinders Actually Explore
Three algorithms can find the same shortest path and still do wildly different amounts of work getting there. Here is exactly how many cells each one explores — and how much its path costs — measured on one grid by the code behind the Pathfinding Visualizer.
· 6 min read · every number counted from the shipped visualizer code
Three Ways to Search a Grid
Breadth-first search expands outward in rings, one step at a time, and stops the moment it reaches the goal. On an unweighted grid that guarantees the fewest-steps path — but it treats the goal like any other direction, so it fans out across the whole board. It needs no priority queue, just a plain queue, which is why it is the simplest of the three.
Dijkstra's algorithm replaces the ring with a priority queue ordered by cost-so-far, so it always expands the cheapest-to-reach cell next. That makes it correct when cells cost different amounts to enter — the difference between a road and a swamp — but it still spreads in every direction, because it has no notion of where the goal is.
A* adds one thing to Dijkstra: a heuristic estimate of the distance still to go — here the Manhattan distance to the goal. It orders its queue by cost-so-far plus that estimate, so it leans toward the goal instead of expanding evenly. When the heuristic never overestimates, A* returns the same optimal path as Dijkstra while touching a fraction of the cells.
What We Actually Measured
The grid is the visualizer's default: 25 columns by 15 rows, start on the left, goal 18 cells to the right. Running the shipped search on it — first open, then with a block of costly cells in the way — gives the counts below.
Cells explored on an open grid
All three return the same optimal 18-step path. A* (blue) touches 19 cells; BFS and Dijkstra fan out across most of the 375-cell grid. With no obstacles, the heuristic does all the work — A* walks almost straight to the goal.
Add a swamp: a 7×7 block of cost-8 cells
| Algorithm | Cells explored | Steps | True path cost |
|---|---|---|---|
| BFS | 260 | 18 | 67 |
| Dijkstra | 330 | 26 | 26 |
| A* | 110 | 26 | 26 |
This is where BFS falls apart. It found an 18-step path — the fewest steps — but that path drives straight through the swamp, and walking it actually costs 67. BFS never sees the cost; it only counts steps, so on weighted terrain it confidently returns the expensive route.
Dijkstra and A* both route around the heavy block for a true cost of 26 — the same optimal answer. The difference between them is effort: Dijkstra expanded 330 cells, A* only 110. The heuristic cut the search to a third without changing the result, which is the entire reason A* is the default pathfinder in games and maps.
Every count here comes from the visualizer's own search() function run on a fixed 25×15 grid — the same cells-explored and cost figures its on-screen counters report. Open the tool, drop a block of heavy cells between the endpoints, and run all three.
Pathfinding is one of four interactive algorithm visualizers on the site — the others animate sorting, data structures, and game-tree search.
Same measure-first approach, other topics: six sorting algorithms counted and the three search algorithms behind the site's game AIs.
Draw a Maze, Watch Them Solve It
Draw walls and heavy cells, drop the start and goal anywhere, and run BFS, Dijkstra and A* — the frontier and the counters update live.
Common questions
What is the difference between BFS, Dijkstra and A*?
All three find a route from a start cell to a goal, but they optimize different things and explore different amounts of the grid. Breadth-first search (BFS) finds the path with the fewest steps and ignores cell weights. Dijkstra's algorithm finds the lowest-cost path when cells cost different amounts to enter. A* is Dijkstra plus a heuristic estimate of the remaining distance, so it heads toward the goal instead of expanding in all directions — same optimal answer, far fewer cells explored.
Is A* always faster than Dijkstra?
A* explores fewer cells than Dijkstra whenever its heuristic is useful, and never more when the heuristic is admissible (never overestimates). On an open 25×15 grid the visualizer's A* settled just 19 cells to reach the goal, versus 273 for Dijkstra — about 14× fewer — and returned the identical shortest path. On the weighted grid A* explored 110 cells against Dijkstra's 330. With a useless (always-zero) heuristic, A* degenerates into exactly Dijkstra.
Why does BFS find a worse path on a weighted grid?
Because BFS counts steps, not cost. On a grid with a block of "heavy" cells (cost 8 each) between start and goal, BFS charged straight through — a 18-step path that actually costs 67 to walk. Dijkstra and A* routed around the heavy cells for a true cost of 26. BFS is optimal only when every cell costs the same; add weights and it optimizes the wrong quantity.
When should I use BFS instead of Dijkstra or A*?
Use BFS when the grid is unweighted — every move costs the same — because then fewest-steps and lowest-cost are the same thing, and BFS is simpler and needs no priority queue. The moment cells have different costs (terrain, traffic, difficulty), switch to Dijkstra, or to A* if you have a reasonable distance heuristic like Manhattan distance on a grid.
What is an admissible heuristic?
A heuristic is admissible if it never overestimates the true remaining cost to the goal. Manhattan distance — the number of horizontal plus vertical steps ignoring obstacles — is admissible on a 4-connected grid, because you can never reach the goal in fewer moves than that. Admissibility is what guarantees A* still returns the optimal path while exploring less of the grid.
Were these numbers measured or estimated?
Measured. The cell-counts and path costs come from running the pathfinding visualizer's own search function on a fixed 25×15 grid — an open one and one with a 7×7 block of heavy cells — and counting the cells each algorithm expanded and the cost of the path it returned. The same counters appear live on the tool.