189. Dijkstra's Shortest Path From a Source

Given an undirected weighted graph with n vertices (0-indexed), m edges (each u, v, weight - all weights non-negative), and a source vertex, find the shortest distance from the source to every vertex. Print the n distances, space-separated, in vertex order; print 'INF' for any vertex unreachable from the source.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains three space-separated integers u, v, and weight (non-negative). The final line contains the source vertex. Output: Print n space-separated distances from the source to every vertex in vertex order, using 'INF' for any unreachable vertex.

1 <= n <= 10^5, 0 <= weight <= 10^4

The 'once popped, distance is final' guarantee is the ENTIRE reason Dijkstra is faster than Bellman-Ford - it never needs to revisit or re-relax an already-finalized vertex, which is precisely the property that breaks down the moment negative weights are allowed.

Find the shortest distance from a source vertex to every other vertex, in a graph with non-negative edge weights. Brute force: Try every possible path from the source to each destination directly and take the shortest - this is exponential in the worst case, when a systematic greedy approach finds all shortest distances efficiently. Optimised: Always extending the CURRENTLY closest unfinished vertex (via a min-heap) guarantees that once a vertex is popped, its distance is FINAL and can never be improved further - this greedy finalization only works correctly because all edge weights are non-negative, ensuring no future relaxation could ever find a shorter path to an already-finalized vertex.

Maintain a dist[] array initialized to infinity except the source (0), and a visited[] array. Repeatedly scan all n vertices to find the unvisited vertex with the smallest current distance, mark it visited, and relax all of its outgoing edges (updating a neighbor's distance if going through this vertex is shorter). Repeating this n times guarantees every vertex is finalized in order of increasing distance, which is correct, but the linear scan to find the next minimum costs O(n) every time regardless of how many edges the graph actually has. Time: O(n^2 + m) Space: O(n + m)

Replace the linear scan with a binary min-heap keyed on current distance: push the source with distance 0, and repeatedly pop the minimum, relaxing its edges and pushing any improved neighbor distances back onto the heap (allowing duplicate, stale entries that get skipped once popped if already finalized). This turns the O(n) 'find minimum' step into an O(log n) heap operation, which is a major win once the graph is sparse (m much smaller than n^2). Time: O((n + m) log n) Space: O(n + m)

Use a Fibonacci heap (or an equivalent structure supporting amortized O(1) decrease-key) instead of a binary heap, so that improving a vertex's tentative distance in place costs O(1) amortized instead of O(log n), while extracting the minimum still costs O(log n). Since there are up to m decrease-key operations but only n extract-min operations, this shifts the dominant cost away from the more frequent operation, giving the theoretically fastest known asymptotic bound for Dijkstra's algorithm. Time: O(m + n log n) Space: O(n + m)

1. Use a min-heap keyed by 'current best known distance', starting with just the source at distance 0. 2. Repeatedly EXTRACT the closest unfinished vertex, and RELAX its edges (check if going through it offers a shorter path to its neighbors). 3. Once a vertex is popped (finalized), its distance never needs to change again.

Time: O((n + m) log n) - each vertex is popped once (O(log n) each) and each edge triggers at most one relaxation (also O(log n) each, for the heap update). Space: O(n), for the distance array and the min-heap.

an edge weight of 0, a vertex unreachable from the source (print 'INF'), and n at its maximum of 10^5 with weights up to 10^4 to confirm the heap-based approach runs efficiently.

Be ready to explain PRECISELY why Dijkstra fails with negative edge weights (a vertex could be popped as 'finalized' before a later negative-weight edge reveals an even shorter path to it) - this is exactly why Bellman-Ford exists as the negative-weight-tolerant alternative.