190. Bellman-Ford - Detect a Negative-Weight Cycle

Given a directed weighted graph with n vertices, m edges (each u, v, weight - weights may be negative), and a source vertex, print 'Yes' if there is a negative-weight cycle reachable from the source, otherwise 'No'.

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 (an edge with weight w, which may be negative). This is followed by a line with the source vertex. Output: Print 'Yes' if a negative-weight cycle reachable from the source exists, otherwise print 'No'.

1 <= n <= 10^4

This negative-cycle check only detects cycles REACHABLE FROM THE GIVEN SOURCE - a negative cycle that exists elsewhere in the graph, but isn't reachable from the source, wouldn't be detected by this specific check (since Bellman-Ford only ever explores from the source outward).

Check whether a graph has a negative-weight cycle reachable from a given source. Brute force: Try to trace every possible cycle in the graph and sum its weights directly - this is combinatorially expensive to enumerate exhaustively, when the extra-round Bellman-Ford check detects negative cycles directly as a byproduct of the standard algorithm. Optimised: Since n-1 rounds are mathematically GUARANTEED to be enough for correct shortest distances if no negative cycle exists, ANY further improvement possible in an (n)th round is undeniable proof that a negative cycle is present somewhere reachable from the source - distances would keep improving forever without ever truly stabilizing, since each additional trip around the negative cycle makes the total even more negative.

Use the Shortest Path Faster Algorithm: start a queue with just the source at distance 0, and whenever relaxing an edge improves a vertex's distance, push that vertex onto the queue (if not already queued) so its outgoing edges get re-examined. Track how many times each vertex is enqueued; if any vertex is enqueued n or more times, it means distances kept improving beyond what's possible without a negative cycle, so one is reachable from the source. This only revisits vertices whose distances actually changed, which is typically much faster in practice than blindly relaxing every edge on every round, though its worst case matches standard Bellman-Ford. Time: O(V * E) Space: O(V + E)

Initialize distance to the source as 0 and all else as infinity, then relax every edge (V-1) times in fixed order - after V-1 passes, all true shortest paths (which can have at most V-1 edges if no negative cycle exists) are finalized. Perform one more full pass over all edges; if any edge (u, v, w) still allows dist[u] + w < dist[v] where u is reachable from the source (dist[u] is finite), a negative-weight cycle reachable from the source exists, so print 'Yes', otherwise 'No'. This is the standard, deterministic way to both compute shortest paths and certify their correctness in one bounded procedure. Time: O(V * E) Space: O(V)

Run the Floyd-Warshall algorithm to compute shortest distances between every pair of vertices, allowing intermediate relaxations through all vertices. If any vertex k that is reachable from the source ends up with dist[k][k] < 0, a negative cycle reachable from the source exists. This correctly detects negative cycles anywhere in the graph, but computing all-pairs distances is much more work than the problem needs, since only reachability from a single source matters. Time: O(n^3) Space: O(n^2)

1. Run the standard (n-1) rounds of Bellman-Ford relaxation to compute shortest distances, ASSUMING no negative cycle exists. 2. Run ONE MORE (nth) round: if ANY edge can STILL be relaxed (found even shorter), that means the assumption was wrong. 3. A negative-weight cycle reachable from the source must exist, since distances should have already stabilized after n-1 rounds otherwise.

Time: O(n * m) - the same complexity as standard Bellman-Ford, just with one additional round of checking. Space: O(n), for the distance array.

Test a negative cycle that exists in the graph but isn't reachable from the given source (expect 'No'), a graph with no edges, and n at the upper bound of 10^4.

Be ready to explain WHY exactly n rounds (not n-1) is the magic number for detection - n-1 rounds handles all legitimate shortest paths (which use at most n-1 edges), so any improvement possible in the nth round can ONLY be explained by a cycle that keeps reducing the total weight indefinitely.