Back to Routing
Dijkstra's Algorithm
Shortest path algorithm for weighted graphs
Algorithm Type
Greedy shortest path
Time Complexity
O((V + E) log V)
Use Case
Network routing protocols
Graph Configuration
0 → 1 (w: 4)
0 → 2 (w: 2)
1 → 2 (w: 1)
1 → 3 (w: 5)
2 → 3 (w: 8)
2 → 4 (w: 10)
3 → 4 (w: 2)
Graph Visualization
Source
Current
Visited
Unvisited
Algorithm Steps
Algorithm Explanation
How Dijkstra's Algorithm Works:
- 1. Initialize: Set distance to source as 0, all others as infinity
- 2. Select: Choose unvisited vertex with minimum distance
- 3. Update: Update distances to all adjacent unvisited vertices
- 4. Mark: Mark current vertex as visited
- 5. Repeat: Continue until all vertices are visited
Key Properties:
- • Greedy Choice: Always selects minimum distance vertex
- • Optimal Substructure: Shortest path has shortest subpaths
- • No Negative Weights: Algorithm assumes all weights ≥ 0
- • Single Source: Finds shortest paths from one source to all vertices
- • Time Complexity: O(V²) with array, O(V log V) with heap