Dijkstra's Algorithm
Dijkstra finds the shortest path from a source to all other nodes in a weighted graph with non-negative edge weights, using a greedy approach with a min-heap.
Dijkstra = a greedy GPS. It always expands the closest unvisited city first, like a growing ink blot on a map. It never revisits -- once a city is 'locked in' as closest, that's final (breaks if roads have negative tolls).
Algorithm: initialize dist[source]=0, all others=infinity. Push (0, source) to min-heap. While heap not empty: pop (d, u). If d > dist[u], skip (stale entry). For each neighbor v with edge weight w: if dist[u]+w < dist[v], update dist[v] and push (dist[v], v) to heap. Time: O((V+E) log V) with a binary heap. Does NOT work with negative edge weights — use Bellman-Ford (O(VE)) for that.
The greedy correctness argument: once a node is popped from the min-heap with distance d, d is guaranteed to be the shortest distance. This holds only for non-negative weights — a negative edge could create a shorter path through a node already finalized. Dijkstra with a Fibonacci heap achieves O(E + V log V), better for dense graphs. Bidirectional Dijkstra halves the search space. A* adds a heuristic function to guide search toward the target — Dijkstra is A* with heuristic=0. For k-th shortest path, use Yen's algorithm or a modified heap with at-most-k-visits per node.
Dijkstra is for shortest paths in weighted graphs with non-negative weights. I implement it with a min-heap of (distance, node) pairs. The lazy deletion approach — push duplicate entries and skip stale ones on pop — is simpler than a decrease-key operation and works fine for interviews. I always verify: no negative weights? Use Dijkstra. Negative weights but no negative cycles? Use Bellman-Ford. Negative cycles? Problem is undefined for shortest path.
Dijkstra FAILS with negative edge weights. It can incorrectly finalize a node's distance before a shorter path through a negative edge is discovered. Also: when using a heap without decrease-key, the same node can appear multiple times — check if the popped distance matches current dist[node] before processing.