Pathfinding Algorithm Visualizer
Draw walls and obstacles on a grid, pick an algorithm, and watch it explore step by step. Compare BFS, DFS, Dijkstra, and A* to see how each finds a path from start to end.
Explores all neighbors at the current depth before moving deeper. Guarantees the shortest path on unweighted grids. Guarantees shortest path.
Metrics
0
Cells Explored
Breadth-First Search (BFS)
Time: O(V + E)
Optimal (guarantees shortest path)
Legend
Reference Guide
BFS and DFS
Breadth-First Search explores all cells at distance 1, then distance 2, and so on. It uses a queue (FIFO) and guarantees the shortest path on an unweighted grid because it visits closer cells first.
Depth-First Search follows one branch as far as possible before backtracking. It uses a stack (LIFO). It finds a path but not necessarily the shortest one, and may explore far more cells than needed.
Both run in O(V + E) time where V is the number of cells and E is the number of edges.
Dijkstra's Algorithm
Dijkstra's algorithm explores cells in order of increasing total cost from the start. It uses a priority queue to always process the cheapest unvisited cell next.
On an unweighted grid (all costs = 1), Dijkstra behaves identically to BFS. The difference appears when cells have different weights: Dijkstra finds the path with the minimum total cost.
Time complexity is O((V + E) log V) with a priority queue. It never overestimates cost, so it always finds the optimal path.
A* Search
A* combines Dijkstra's exact cost tracking with a heuristic estimate of the remaining distance. It evaluates cells by f(n) = g(n) + h(n), where g is the cost so far and h is the heuristic.
With an admissible heuristic (one that never overestimates), A* is guaranteed to find the shortest path. Manhattan distance is the standard admissible heuristic for 4-directional grids.
A* typically explores far fewer cells than Dijkstra or BFS because the heuristic guides it toward the goal. This makes it the go-to algorithm for game AI and robotics.
Heuristics and Optimality
A heuristic h(n) estimates the cost from node n to the goal. It is admissible if it never overestimates the true cost. An admissible heuristic guarantees A* finds the optimal path.
Manhattan distance (|x1-x2| + |y1-y2|) is admissible for 4-directional grids because you can only move horizontally or vertically.
Euclidean distance is also admissible but less tight, meaning A* may explore more cells. A tighter heuristic means fewer cells explored and faster search.
If h(n) = 0 for all n, A* degrades to Dijkstra. If h(n) is the true cost, A* goes straight to the goal with zero wasted exploration.