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.