Pathfinding: Dijkstra & A*
Dijkstra floods a grid in every direction while A* aims straight at the goal. Race them on the same maze and see why a good heuristic visits far fewer cells for the same shortest path.
Dijkstra and A*
Both algorithms find the same shortest path on this grid. The difference is how much of the map they explore on the way. Toggle between them, then step or play the search and watch the visited region change shape.
A* is ready: priority = g + h
A* orders its frontier by f = g + h, where g is the true cost from the start and h is the Manhattan estimate to the goal. Because h points toward the goal, A* expands cells that look promising first. Step through to watch the frontier lean toward the goal.
Why A* explores less
On the current walls A* touches 53% fewer cells than Dijkstra yet returns a path of the same length. The heuristic h is the whole reason: it adds an estimate of the remaining distance to each cell’s priority, so the queue keeps handing back cells that head toward the goal instead of cells that merely sit close to the start. Because Manhattan distance never overestimates the true cost (it is admissible), A* can prune those detours without ever risking the optimal answer. Drop walls in front of the goal and the gap widens; in an open room with no walls the two look nearly identical because there are no detours to skip.
4-neighbour movement, uniform step cost of 1, Manhattan-distance heuristic. Click or drag to draw and erase walls; the search recomputes live.