What is Dijkstra's Algorithm?
Dijkstra's algorithm finds the shortest path from a single source to all other nodes in a weighted graph. Invented by Edsger Dijkstra in 1956, it powers real-world applications like GPS navigation and network routing.
Why Does It Matter?
Dijkstra's algorithm is essential in both coding interviews and real-world systems.
- •Real-world use: GPS navigation, network routing protocols (OSPF), game AI pathfinding
- •Interview staple: Frequently tested at Google, Amazon, Meta, and top tech companies
- •Foundation: Basis for advanced algorithms like A*, Bellman-Ford understanding
How It Works
Dijkstra's uses a greedy strategy — at each step, it picks the unvisited node with the smallest known distance.
Step 1. Set the starting node's distance to 0, all others to infinity.
Step 2. Pick the unvisited node with the smallest distance.
Step 3. Update distances to its neighbors:
- •New distance = current node distance + edge weight
- •If new distance < existing distance, update it
Step 4. Repeat steps 2-3 until all nodes are visited.
Time Complexity
| Implementation | Time Complexity |
|---|---|
| Array-based | O(V²) |
| Priority Queue (Heap) | O((V + E) log V) |
For large graphs, always use a min-heap priority queue. It retrieves the closest node in O(log V) instead of O(V).
See Priority Queue Visualization →
The Key Limitation
Dijkstra's cannot handle negative edge weights. It relies on the greedy assumption that once a shortest distance is finalized, it won't change. Negative weights break this assumption.
For graphs with negative weights, use the Bellman-Ford algorithm instead.
See Bellman-Ford Visualization →
Comparison with Other Shortest Path Algorithms
| Algorithm | Negative Weights | Time Complexity | Use Case |
|---|---|---|---|
| Dijkstra | No | O((V+E) log V) | Single source |
| Bellman-Ford | Yes | O(V × E) | Single source + negatives |
| Floyd-Warshall | Yes | O(V³) | All-pairs shortest path |
Pro Tips
- •Skip nodes from the priority queue whose distance is already greater than the finalized distance (saves time)
- •To reconstruct the path, maintain a prev array recording the predecessor of each node
- •Works on 2D grids too — treat each cell as a node with weighted edges
See It in Action on AlgoNote
Watch Dijkstra's algorithm finalize nodes one by one, updating shortest distances in real time on AlgoNote. Modify edge weights and see how the optimal path changes.