Pathfinding Algorithm Visualizer

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 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* 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.

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.