About Dijkstra's Shortest Path
Dijkstra's algorithm finds the shortest paths from a source node to all other nodes in a weighted graph. It works by maintaining a priority queue of tentative distances and greedily selecting the closest unvisited node at each step. It requires all edge weights to be non-negative.
Complexity Analysis
- Time Complexity
- O((V + E) log V)
- Space Complexity
- O(V)
- Difficulty
- advanced
Key Concepts
Greedy Strategy
Dijkstra's greedily picks the unvisited node with the smallest tentative distance. This works because with non-negative weights, once we process a node, we've already found its shortest path.
Relaxation
When we find a shorter path to a node through a newly processed node, we 'relax' the edge by updating the distance. This is the core operation: dist[v] = min(dist[v], dist[u] + weight(u,v)).
Priority Queue
The priority queue efficiently extracts the minimum-distance node. Using a binary heap gives O(log V) extraction and insertion.
Non-Negative Weights Required
Dijkstra's fails with negative edge weights because the greedy assumption breaks. Use Bellman-Ford for graphs with negative edges.
Common Pitfalls
Negative edge weights
If any edge has a negative weight, Dijkstra's can produce incorrect results. Always verify all weights ≥ 0.
Stale PQ entries
When using a simple heap, the same node may appear multiple times. Always check if visited when extracting.