Shortest Path Solver
Find shortest path between nodes using Dijkstra's algorithm
Enter Your Problem
Enter edge weights (0 means no edge). Distance from node i to node j.
| From\To | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 |
Theory of Shortest Path Problems
Example Problem:
Problem: Find shortest path from Node 1 to Node 5
Graph Structure:
- Node 1 → Node 2: weight 4
- Node 1 → Node 3: weight 2
- Node 2 → Node 3: weight 1
- Node 2 → Node 4: weight 5
- Node 3 → Node 4: weight 8
- Node 3 → Node 5: weight 10
- Node 4 → Node 5: weight 2
Step-by-Step Solution Preview:
1. Initialize: distance[1] = 0, all others = ∞
2. Visit Node 1: Update distances to nodes 2 and 3
3. Visit Node 3 (closest): Update distances to nodes 4 and 5
4. Visit Node 2: Update distance to node 4 (better path found)
5. Visit Node 4: Update distance to node 5
Result: Path 1→2→4→5 with total distance = 11
1. What is the time complexity of Dijkstra's algorithm?
2. What condition must be satisfied for Dijkstra's algorithm to work correctly?
3. What does Dijkstra's algorithm find?
4. Which data structure is commonly used to implement Dijkstra's algorithm efficiently?