388. Bellman-Ford - Shortest Paths From a Source

Given a directed weighted graph with n vertices (0-indexed), m edges (each u, v, weight - weights may be negative, but it's guaranteed no negative-weight cycle is reachable from the source), and a source vertex, find the shortest distance from the source to every vertex using the Bellman-Ford algorithm. Print the n distances, space-separated, in vertex order; print 'INF' for any vertex unreachable from the source.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains three integers u v w, a directed weighted edge (weights may be negative, with no negative cycle reachable from the source). This is followed by a line with the source vertex. Output: Print the n shortest distances from the source, space-separated in vertex order, printing 'INF' for any unreachable vertex.

1 <= n <= 10^4

Explicitly skipping relaxation from a still-infinity-distance vertex (rather than computing infinity + weight and treating the overflow/wraparound as some huge but finite number) is an important implementation detail - a coding mistake here can silently produce wrong, non-infinite distances for genuinely unreachable vertices.

Find the shortest distance from a source vertex to every other vertex, even when some edge weights are negative. Brute force: Try every possible path from the source to each vertex directly and take the minimum - this is exponential, when Bellman-Ford's repeated-relaxation approach finds all shortest distances in polynomial time even with negative weights present. Optimised: Repeating the relaxation process EXACTLY (n-1) times guarantees correctness because the longest possible SIMPLE shortest path (no repeated vertices) in a graph with n vertices can have at most (n-1) edges - so after (n-1) rounds, every possible shortest path length has been fully accounted for, unlike Dijkstra's greedy approach which can be fooled by negative weights.

For each vertex, recursively explore every simple path (no repeated vertices) from the source, summing edge weights along the way, and keep the minimum total reaching that vertex. This is necessary as a 'brute' baseline specifically because negative edge weights rule out Dijkstra-style greedy shortest-path search (a locally shortest prefix isn't guaranteed to lead to the globally shortest path), so naively it seems every simple path must be considered - but the number of simple paths in a graph can be exponential, making this impractical beyond tiny graphs. Time: O(2^n) in the worst case Space: O(n) recursion depth

Instead of blindly relaxing all m edges in every one of the n-1 rounds, keep a queue of vertices whose distance was just improved and only re-examine the outgoing edges of those vertices (enqueuing any further vertex that gets updated as a result), stopping once the queue empties. This still has the same worst-case bound as classic Bellman-Ford (and remains correct for the same reason - no negative cycle reachable from the source), but in practice it skips relaxing edges from vertices whose distance hasn't changed, making it noticeably faster than doing full sweeps on typical graphs. Time: O(n*m) worst case, typically much less Space: O(n)

Initialise the source's distance to 0 and everything else to infinity, then relax every one of the m edges (checking if going through it improves the destination's known distance) in n-1 full passes over the edge list; because any shortest path uses at most n-1 edges, n-1 rounds of relaxing every edge is guaranteed to have propagated the true shortest distances everywhere reachable, correctly handling negative weights (as long as there's no negative cycle) unlike Dijkstra. This is the standard, reliable implementation of the algorithm. Time: O(n*m) Space: O(n)

1. Initialize the source's distance to 0 and every other vertex to infinity. 2. RELAX every single edge, REPEATED (n-1) times total - after k rounds, every shortest path using AT MOST k edges is guaranteed correct. 3. Skip relaxing an edge whose starting vertex still has distance infinity, since adding a finite weight to infinity must stay infinity.

Time: O(n * m) - (n-1) rounds, each relaxing all m edges. Space: O(n), for the distance array.

Test a vertex unreachable from the source (printed as 'INF'), negative edge weights present as in the example, and n at the upper bound of 10^4.

Be ready to explain why Bellman-Ford correctly handles negative weights while Dijkstra doesn't - Bellman-Ford never 'finalizes' a vertex prematurely, instead repeatedly re-checking every edge, which naturally accommodates a later-discovered shorter path through a negative edge.