Back to Network Layer
Dijkstra's Algorithm
Shortest path algorithm for weighted graphs
Algorithm Type
Greedy shortest path
Time Complexity
O((V + E) log V)
Use Case
Routing protocols (OSPF)
Algorithm Controls
Graph Visualization
Start Node
Target Node
Current Node
Visited
Dijkstra's Algorithm Explanation
How It Works
- 1. Initialize: Set distance to start node = 0, all others = ∞
- 2. Select: Choose unvisited node with minimum distance
- 3. Update: Calculate distances to all neighbors
- 4. Mark: Mark current node as visited
- 5. Repeat: Continue until all nodes visited or target reached
Applications
- • Network routing protocols (OSPF)
- • GPS navigation systems
- • Social network analysis
- • Flight connection systems
- • Game pathfinding
Key Properties
- • Greedy algorithm approach
- • Works with non-negative weights
- • Guarantees shortest path
- • Single-source shortest path
- • Optimal substructure property