Interactive Visualizers
Explore algorithms through interactive visualizations
Shortest Path Algorithms
Visualize and compare different shortest path algorithms including BFS, Dijkstra, Bellman-Ford, and Floyd-Warshall.
N-Queens Problem
Watch the backtracking algorithm solve the classic N-Queens problem step by step on an interactive chessboard.
Algorithm Theory & Concepts
Shortest Path Algorithms
Breadth-First Search (BFS)
Use Case: Unweighted graphs, finding shortest path with minimum edges
Key Concept: Explores nodes level by level, guaranteeing shortest path in unweighted graphs
How it works:
- Uses a queue to store nodes to visit
- Visits all neighbors at current depth before moving deeper
- First time a node is reached = shortest path found
Dijkstra's Algorithm
Use Case: Weighted graphs with non-negative edge weights
Key Concept: Greedy approach, always selects unvisited node with minimum distance
Applications:
- GPS navigation systems (Google Maps, Waze)
- Network routing protocols
- Game pathfinding
Bellman-Ford Algorithm
Use Case: Weighted graphs with negative edge weights
Key Concept: Dynamic programming approach, can detect negative cycles
Advantages over Dijkstra:
- Handles negative weight edges
- Detects negative cycles
- More versatile but slower
Floyd-Warshall Algorithm
Use Case: All-pairs shortest paths in weighted graphs
Key Concept: Dynamic programming, finds shortest paths between all vertex pairs
When to use:
- Need distances between all node pairs
- Dense graphs where V² ≈ E
- Small to medium-sized graphs
N-Queens Problem
Problem Statement
Place N queens on an N×N chessboard such that no two queens attack each other. Queens can attack horizontally, vertically, and diagonally.
Constraints:
- No two queens in the same row
- No two queens in the same column
- No two queens on the same diagonal
Backtracking Solution
The N-Queens problem is solved using backtracking - a systematic way of trying all possibilities until a valid solution is found.
Algorithm Steps:
- Start with the first row
- Place a queen in the first safe column
- Move to the next row and repeat
- If no safe position exists, backtrack to previous row
- Continue until all queens are placed or no solution exists
Complexity & Applications
Time Complexity: O(N!) in worst case
Space Complexity: O(N) for the solution array
Real-world Applications:
- Resource allocation problems
- Task scheduling with conflicts
- Network design and placement
- VLSI design and circuit placement
Algorithm Comparison
| Algorithm | Time Complexity | Space Complexity | Type | Use Case |
|---|---|---|---|---|
| BFS | O(V + E) | O(V) | Unweighted | Shortest path, minimum edges |
| Dijkstra | O(E + V log V) | O(V) | Non-negative weights | GPS, network routing |
| Bellman-Ford | O(V × E) | O(V) | Negative weights allowed | Negative cycle detection |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest path | Dense graphs, all distances |
| N-Queens | O(N!) | O(N) | Constraint satisfaction | Backtracking, scheduling |