Stage 1 · Code
Graph Algorithms
Dijkstra
Single-source shortest paths with non-negative weights.
7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Algorithm
Dijkstra finds shortest paths from source to all vertices in graph with non-negative edge weights. Greedy: always pick unvisited node with smallest known distance. Uses priority queue (min-heap) for O((V+E)log V).
Implementation
Godijkstra-with-min-heap.go
41 linesLn 1, Col 1Go
Min-heap stores (distance, node). Lazy deletion: skip if popped distance > current known distance. Process each node at most once per better distance found.
Variants
| Variant | Description | Complexity |
|---|---|---|
| Standard | All shortest paths from source | O((V+E)log V) |
| Early exit | Stop when target popped | O((V+E)log V) worst |
| Path reconstruction | Track parent array | Same |
| A* search | Heuristic (e.g., Euclidean) to guide | O((V+E)log V) worst |
| Multi-source | Start with multiple sources at dist 0 | Same |
| Modified Dijkstra | Minimize max edge, count paths, etc. | Same |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.