Graph Algorithm Visualization
Explore pathfinding algorithms with interactive grid visualization
Legend
- Select an algorithm from the sidebar dropdown.
- Adjust grid size and wall density to customize the maze.
- Click on cells to manually add or remove walls.
- Click "Start Search" to visualize the pathfinding algorithm.
- Use "Step" to advance one iteration at a time for detailed analysis.
- The stats bar shows real-time metrics during the search.
- Different colors represent different states (see Legend).
Algorithm Background
Graph Theory and Pathfinding
Graph algorithms are fundamental to computer science and have applications ranging from GPS navigation to network routing, game AI, and social network analysis. A graph consists of vertices (nodes) connected by edges. In our grid visualization, each cell is a vertex, and adjacent cells are connected by edges.
The pathfinding problem seeks to find a sequence of vertices connecting a start vertex to a goal vertex. Different algorithms employ different strategies—some prioritize finding any path quickly, while others guarantee finding the shortest path.
Depth-First Search (DFS)
Strategy: DFS explores as far as possible along each branch before backtracking. It uses a stack (either explicit or via recursion) to remember which vertices to visit next.
Algorithm:
1. Start at the initial vertex and mark it as visited
2. For each unvisited neighbor, recursively apply DFS
3. Backtrack when no unvisited neighbors remain
Complexity:
- Time: O(V + E) where V = vertices, E = edges
- Space: O(V) for the recursion stack or explicit stack
Characteristics: DFS does not guarantee finding the shortest path. It explores deeply before exploring broadly, making it memory efficient but potentially slow if the goal is down a wrong branch. Useful for maze generation, detecting cycles, and topological sorting.
Applications: Solving puzzles, detecting connected components, generating mazes, topological sorting, and finding strongly connected components in directed graphs.
Breadth-First Search (BFS)
Strategy: BFS explores all vertices at distance k from the start before exploring vertices at distance k+1. It uses a queue to process vertices in the order they are discovered.
Algorithm:
1. Enqueue the start vertex and mark it as visited
2. While queue is not empty:
a. Dequeue a vertex v
b. For each unvisited neighbor u of v:
- Mark u as visited
- Enqueue u
- Record parent for path reconstruction
Complexity:
- Time: O(V + E)
- Space: O(V) for the queue
Characteristics: BFS guarantees finding the shortest path in unweighted graphs. It explores layer by layer, ensuring all shorter paths are considered first. More memory-intensive than DFS for deep graphs but optimal for shortest-path problems.
Applications: Finding shortest paths in unweighted graphs, web crawling, social networking (degrees of separation), broadcasting in networks, and GPS navigation in uniform cost scenarios.
Dijkstra's Algorithm
Strategy: Dijkstra's algorithm finds the shortest path in weighted graphs where edge weights are non-negative. It maintains a priority queue of vertices ordered by their tentative distance from the start.
Algorithm:
1. Initialize distance to start as 0, all others as ∞
2. Add all vertices to a priority queue (min-heap)
3. While queue is not empty:
a. Extract vertex u with minimum distance
b. For each neighbor v of u:
- Calculate: alt = dist[u] + weight(u, v)
- If alt < dist[v]: update dist[v] = alt
Mathematical Formulation:
dist[v] = min(dist[v], dist[u] + w(u,v))
where w(u,v) is the weight of edge from u to v
Complexity:
- Time: O((V + E) log V) with binary heap, O(V²) with array
- Space: O(V)
Characteristics: Dijkstra's algorithm guarantees finding the shortest path in weighted graphs with non-negative edge weights. It's a greedy algorithm that always expands the most promising vertex (lowest distance so far).
Applications: GPS and map routing, network routing protocols (OSPF), robot path planning, airline flight routing, and any scenario requiring optimal paths with varying costs.
Limitation: Cannot handle negative edge weights. For graphs with negative weights (but no negative cycles), use the Bellman-Ford algorithm instead.
A* (A-Star) Algorithm
Strategy: A* is an informed search algorithm that uses a heuristic function to guide its search toward the goal more efficiently than Dijkstra's. It combines the actual cost from the start with an estimated cost to the goal.
Core Formula:
f(n) = g(n) + h(n)
where:
• g(n) = actual cost from start to node n
• h(n) = heuristic estimate of cost from n to goal
• f(n) = estimated total cost of path through n
Common Heuristics:
- Manhattan Distance: |x₁ - x₂| + |y₁ - y₂| (for grid with 4-directional movement)
- Euclidean Distance: √[(x₁ - x₂)² + (y₁ - y₂)²] (straight-line distance)
- Chebyshev Distance: max(|x₁ - x₂|, |y₁ - y₂|) (for grid with 8-directional movement)
Algorithm:
1. Initialize open set with start node (f = h(start))
2. While open set is not empty:
a. Select node n with lowest f(n)
b. If n is goal, reconstruct and return path
c. Move n to closed set
d. For each neighbor m of n:
- If m in closed set, skip
- Calculate tentative g(m) = g(n) + cost(n,m)
- If m not in open set or tentative g(m) < g(m):
Update g(m), f(m) = g(m) + h(m), add to open set
Complexity:
- Time: O(b^d) in worst case, but typically much better with good heuristic
- Space: O(b^d) where b is branching factor, d is solution depth
Optimality Guarantee: A* is guaranteed to find the optimal path if the heuristic is admissible (never overestimates the actual cost) and consistent (satisfies the triangle inequality: h(n) ≤ cost(n,m) + h(m)).
Characteristics: A* combines the best of Dijkstra's (optimality) and greedy best-first search (speed). The quality of the heuristic directly impacts performance—better heuristics lead to fewer explored nodes.
Applications: Video game pathfinding, robotics, puzzle solving (15-puzzle, Rubik's cube), route planning with landmarks, and any scenario where you can estimate distance to goal.
Algorithm Comparison
| Algorithm | Completeness | Optimality | Time Complexity | Space Complexity |
|---|---|---|---|---|
| DFS | Yes* | No | O(V + E) | O(V) |
| BFS | Yes | Yes** | O(V + E) | O(V) |
| Dijkstra | Yes | Yes | O((V+E) log V) | O(V) |
| A* | Yes | Yes*** | O(b^d) | O(b^d) |
Notes:
* DFS is complete in finite graphs
** BFS finds optimal solution in unweighted graphs
*** A* finds optimal solution with admissible heuristic
When to Use Each Algorithm
Use DFS when:
- You want a memory-efficient solution
- Finding any solution is sufficient (not necessarily shortest)
- Exploring deep branches first makes sense for your problem
- Detecting cycles or connectivity is the goal
Use BFS when:
- You need the shortest path in an unweighted graph
- Finding the closest solution is important
- Level-by-level exploration makes sense
- Broadcasting or propagation problems
Use Dijkstra when:
- You have a weighted graph with non-negative weights
- You need the optimal path considering edge costs
- No heuristic information is available
- Finding shortest paths from one source to all vertices
Use A* when:
- You have weighted edges and a good heuristic function
- Performance is critical and you can estimate goal distance
- Finding the optimal path efficiently is required
- Working with spatial problems (grids, maps)
Real-World Applications
Graph algorithms power many technologies we use daily:
- GPS Navigation: A* and Dijkstra's algorithms find optimal routes considering distance, time, traffic, and road types. Modern systems use contraction hierarchies and other optimizations for faster computation.
- Social Networks: BFS finds connections and degrees of separation. DFS helps detect communities and influencers.
- Game AI: A* powers enemy pathfinding in video games, making NPCs navigate complex environments realistically.
- Network Routing: Internet routers use variants of Dijkstra's algorithm (like OSPF) to find optimal packet routes.
- Recommendation Systems: Graph algorithms analyze user-item relationships to suggest products, movies, or connections.
- Robotics: Path planning algorithms help robots navigate physical spaces while avoiding obstacles.
- Puzzle Solvers: A* and BFS solve puzzles like sliding tiles, Sudoku, and maze problems.