Shortest path in a weighted graph with non-negative edges. Uses a min-heap to always extend the closest unfinished node. O((V + E) log V).
What Is It?
Dijkstra's algorithm finds the shortest path from a single source to all other nodes in a weighted graph (with non-negative edge weights). It works by greedily extending the node with the smallest known distance.
You maintain a distance array (dist[v] = shortest known distance to v) and a min-heap (priority queue). Start with dist[source] = 0, everything else at infinity. Pop the node with the smallest distance, "relax" its neighbors (check if going through this node gives a shorter path), and push updated distances.
The key insight: when you pop a node from the heap, its distance is final. You've already found the shortest path to it. This is why negative edges break the algorithm — they could invalidate a previously finalized distance.