⚙️AlgorithmIntermediate

Bellman-Ford Algorithm

Key Points

•
Bellman–Ford finds single-source shortest paths even when some edge weights are negative.
•
It relaxes every edge repeatedly for V−1 rounds, where V is the number of vertices, to allow paths with up to V−1 edges to improve.
•
If a further relaxation is still possible on round V, a negative-weight cycle is reachable from the source.
•
All vertices reachable from any such cycle effectively have distance −∞ because you can loop to reduce cost without bound.
•
The algorithm runs in O(VE) time and O(V) space for distances and parents, plus O(E) to store edges.
•
You must guard against overflow by not relaxing from nodes at +INF and by using 64-bit integers when weights can be large.
•
Early stopping is safe: if an entire pass makes no changes, the current distances are already optimal.
•
Bellman–Ford is the engine behind feasibility checks for difference constraints and as a subroutine in Johnson’s algorithm.

Prerequisites

→Graphs and directed edges — Understanding vertices, edges, and how to model problems as directed weighted graphs is essential.
→Big-O notation — To analyze the O(VE) time and O(V+E) space complexity.
→Shortest path concept — Knowing what a path is and how path costs accumulate clarifies relaxation and correctness.
→Breadth-first search (BFS) — Used to propagate negative-cycle reachability after detection.
→Priority vs. queue mechanics — Helps contrast Bellman–Ford with Dijkstra’s and understand SPFA heuristics.
→Integer overflow and numeric limits — Essential to safely implement sentinel INF and 64-bit arithmetic.

Detailed Explanation

Tap terms for definitions

01Overview

The Bellman–Ford algorithm is a classic method for computing the shortest path distances from a single source to all vertices in a weighted directed graph, even when some edges have negative weights. Unlike Dijkstra’s algorithm, which assumes nonnegative weights, Bellman–Ford systematically relaxes all edges V−1 times (where V is the number of vertices) so that paths with up to V−1 edges are considered. The key insight is that any simple shortest path can have at most V−1 edges, since repeating a vertex would introduce a cycle. After these V−1 passes, a final pass is used to detect the presence of any negative-weight cycle reachable from the source: if you can still improve a distance, then an endlessly improving (more negative) cycle exists along some reachable path. In such cases, all vertices reachable from that cycle are conceptually at distance −∞ because you can keep looping to reduce the path cost without bound. Bellman–Ford’s time complexity is O(VE), which is slower than Dijkstra’s on sparse graphs, but its ability to handle negative edges and detect negative cycles makes it uniquely powerful. It serves as a building block in more advanced techniques, such as Johnson’s algorithm for all-pairs shortest paths and feasibility checks for systems of difference constraints.

02Intuition & Analogies

Imagine planning a road trip where some roads have tolls (positive cost) and a few offer rebates or cashback (negative cost). If you plan naively with only the best current deals, you might miss a great route that becomes attractive only after chaining several smaller deals together. Bellman–Ford acts like a careful planner who repeatedly rechecks every road deal, allowing multi-step chains of rebates to reveal better overall savings. Each full recheck corresponds to one additional allowed hop in your trip plan. After V−1 rechecks, any simple route involving at most V−1 roads has been considered, so you should have the best prices possible. Now, suppose there is a bizarre promotion loop where you can drive around a small set of roads and end up with more cashback than you started with. Then you could loop forever to make your total cost as negative as you want. Bellman–Ford’s final recheck is specifically designed to spot such a loop: if any route still gets cheaper, you must have encountered a negative cycle. Furthermore, any destination that you can drive to after visiting that loop will have a conceptually unbounded discount (−∞). In practice, the algorithm marks all those destinations as affected by a negative cycle. This “recheck all deals repeatedly, then verify no infinite-discount loops exist” intuition is the heart of Bellman–Ford.

03Formal Definition

Let G = (V, E) be a directed graph with weight function w: E →

R

, and let s ∈ V be the source. Define d[v] as the current estimate of the shortest-path distance from s to v. A relaxation step for edge (u, v) with weight w(u, v) updates

d [v] \leftarrow min (d [v]

, d[u] + w(u, v)). Initialize d[s] = 0 and d[v] = +∞ for

v \neq = s

. The algorithm performs exactly

∣ V ∣

− 1 full passes over all edges, applying relaxation to each. It can be shown that after k passes, d[v] is at most the weight of the shortest

s \to v

path that uses at most k edges. Because any simple shortest path contains at most

∣ V ∣

− 1 edges, after

∣ V ∣

− 1 passes, d[v] equals the true shortest-path distance if no negative-weight cycle is reachable from s. A final pass over all edges checks for any edge (u, v) where d[u] + w(u, v) < d[v]; if such an edge exists, then a negative-weight cycle is reachable from s. In that case, the distances to any vertex reachable from that cycle are undefined in the usual sense and are represented as −∞.

04When to Use

Use Bellman–Ford when your graph may contain negative edge weights or when you must detect negative-weight cycles. It is a reliable choice for graphs with up to roughly 2×10^5 edges in competitive programming if optimized and used judiciously, though input sizes vary by problem. Typical scenarios include currency arbitrage detection (negative log exchange rates), scheduling with gains/penalties, and checking feasibility of difference constraints of the form x_v − x_u ≤ w(u, v). Bellman–Ford is also a necessary component in Johnson’s algorithm to reweight edges before running Dijkstra’s for all-pairs shortest paths. Prefer Dijkstra’s algorithm on nonnegative-weight graphs as it is faster (e.g., O((V + E) log V) with a heap). Prefer Bellman–Ford when correctness with negative edges matters more than speed. If you only need to detect the existence of a negative cycle reachable from a super-source, Bellman–Ford can be slightly simplified since exact distances are not required beyond feasibility.

⚠️Common Mistakes

Forgetting to skip relaxation from vertices with distance +INF. Adding a weight to +INF can overflow or produce meaningless values. Always check if d[u] is finite before d[u] + w(u, v).
Using 32-bit ints for distances when edge weights or path sums can exceed that range. Use 64-bit types (long long) and choose an INF value safely below LLONG_MAX to avoid overflow on additions.
Running fewer than V−1 relaxation passes. That can leave some shortest paths undiscovered, especially those requiring many edges.
Not performing the final “cycle detection” pass. Without it, you might incorrectly report finite distances in the presence of reachable negative cycles.
Failing to propagate the negative-cycle effect. After detecting an edge that can still relax on pass V, you must mark every vertex reachable from any such edge as having distance −∞.
Confusing undirected negative edges with negative cycles. In undirected graphs, a single negative edge instantly creates a negative cycle of length 2; treat undirected inputs as two directed edges.
Over-optimizing with SPFA without safeguards. SPFA can be faster in practice on many inputs but can degrade to O(VE) or worse; know worst-case behavior and add iteration caps if needed.

Key Formulas

k-edge relaxation DP

d_{k} [v] = min (d_{k - 1} [v], (u, v) \in E min {d_{k - 1} [u] + w (u, v)})

Explanation: After k full passes, the best known distance to v equals the minimum over all paths from the source to v that use at most k edges. This recurrence explains why V−1 passes suffice when no negative cycle is reachable.

Negative cycle detection condition

If \exists (u, v) \in E with d [u] + w (u, v) < d [v] after ∣ V ∣ - 1 passes \Rightarrow negative cycle reachable

Explanation: A further improvement beyond the (V−1)-edge limit implies a beneficial cycle is being exploited. That cycle must have negative total weight and be reachable from the source.

Unbounded improvement on negative cycles

e \in C \sum w (e) < 0 \Rightarrow repeating C yields path cost \to - \infty

Explanation: If a directed cycle C has negative total weight, you can loop around C arbitrarily many times to reduce total path cost without bound. Therefore, any vertex reachable after such a cycle has distance −∞.

Time complexity

T (V, E) = O (∣ V ∣∣ E ∣)

Explanation: The algorithm performs |V|−1 full passes over all |E| edges, and a final pass to check for cycles, leading to O(VE) time. This is generally slower than Dijkstra’s on nonnegative graphs.

Space complexity

S (V, E) = O (∣ V ∣ + ∣ E ∣)

Explanation: We store distances and predecessors for all vertices (O(V)) and the edge list (O(E)). Auxiliary arrays for cycle propagation add linear overhead.

Simple path edge bound

Simple path length \leq ∣ V ∣ - 1

Explanation: Any path with more than |V|−1 edges must repeat a vertex and contain a cycle. Thus shortest simple paths have at most |V|−1 edges.

Triangle inequality on shortest paths

d [v] \leq d [u] + w (u, v) \forall (u, v) \in E at termination (no negative cycles)

Explanation: When Bellman–Ford finishes without detecting negative cycles, the distances satisfy all edge constraints. This is the feasibility condition that certifies optimality.

Johnson reweighting via potentials

pot (v) = d [v] \Rightarrow w^{'} (u, v) = w (u, v) + pot (u) - pot (v) \geq 0

Explanation: Using Bellman–Ford distances as vertex potentials reweights all edges to be nonnegative, enabling Dijkstra’s. This works only if no negative cycle exists.

Complexity Analysis

Bellman–Ford processes all edges in each of

∣ V ∣

−1 relaxation rounds, giving O(

∣ V ∣∣ E ∣

) time. The rationale is that after the k-th round, every shortest path with at most k edges has been considered. A final O(

∣ E ∣

) pass checks for further relaxation to detect any reachable negative-weight cycle. While O(VE) can be heavy for dense graphs (E ≈

V^{2}

→ O(

V^{3}

)), it is often acceptable for sparse graphs or moderate input sizes in competitive programming, especially when combined with early stopping: if a full round applies no updates, the algorithm terminates early, effectively yielding O(kE), where k is the number of rounds until stabilization (

k \leq V - 1

). Space-wise, storing distances and predecessors needs O(V). The graph as an edge list uses O(E) space, and optional structures (like a queue or arrays to propagate negative-cycle reachability) add O(V+E) at most. Therefore total space is O(V+E). A practical subtlety is using a sufficiently large INF sentinel and 64-bit types to avoid overflow during d[u] + w(u,v). Skipping relaxations from +INF nodes prevents undefined behavior. When negative cycles are present, extra passes to mark nodes as −∞ require a graph traversal (e.g., BFS/DFS) from initially flagged nodes over outgoing edges, which is O(V+E) and does not change asymptotic complexity. Overall, Bellman–Ford trades speed for generality: it is slower than Dijkstra’s but uniquely handles negative weights and certifies (in)feasibility by detecting negative cycles.

Code Examples

Bellman–Ford with detection and −∞ propagation (edge list input)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge {
5     int u, v;            // from u to v
6     long long w;         // weight
7 };
8 
9 int main() {
10     ios::sync_with_stdio(false);
11     cin.tie(nullptr);
12 
13     int n, m, s; // n vertices (0..n-1), m edges, source s
14     if (!(cin >> n >> m >> s)) {
15         cerr << "Usage: provide n m s followed by m edges (u v w)\n";
16         return 0;
17     }
18 
19     vector<Edge> edges(m);
20     for (int i = 0; i < m; ++i) {
21         int u, v; long long w;
22         cin >> u >> v >> w;
23         edges[i] = {u, v, w};
24     }
25 
26     const long long INF = (long long)4e18; // safe INF to avoid overflow on add
27     vector<long long> d(n, INF);
28     d[s] = 0;
29 
30     // V-1 relaxation rounds
31     for (int i = 0; i < n - 1; ++i) {
32         bool any = false;
33         for (const auto &e : edges) {
34             if (d[e.u] == INF) continue; // unreachable source endpoint
35             if (d[e.v] > d[e.u] + e.w) {
36                 d[e.v] = d[e.u] + e.w;
37                 any = true;
38             }
39         }
40         if (!any) break; // early stopping optimization
41     }
42 
43     // Build adjacency to propagate negative cycle reachability
44     vector<vector<int>> adj(n);
45     for (const auto &e : edges) adj[e.u].push_back(e.v);
46 
47     // Find vertices whose distance can still be improved → on or after a reachable negative cycle
48     vector<int> bad(n, 0);
49     for (const auto &e : edges) {
50         if (d[e.u] == INF) continue;
51         if (d[e.v] > d[e.u] + e.w) {
52             bad[e.v] = 1;
53         }
54     }
55 
56     // Propagate bad marks to everything reachable (they are effectively -INF)
57     queue<int> q;
58     vector<int> vis(n, 0);
59     for (int v = 0; v < n; ++v) if (bad[v]) { q.push(v); vis[v] = 1; }
60     while (!q.empty()) {
61         int u = q.front(); q.pop();
62         for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; q.push(v); }
63     }
64 
65     // Output: if unreachable → INF; if vis[v] → -INF; else finite distance
66     for (int v = 0; v < n; ++v) {
67         if (d[v] == INF) {
68             cout << "INF\n";
69         } else if (vis[v]) {
70             cout << "-INF\n";
71         } else {
72             cout << d[v] << "\n";
73         }
74     }
75     return 0;
76 }
77

Reads a directed weighted graph and a source. Performs V−1 rounds of relaxation over an edge list, with early stopping. Then does one more logical check for improvable edges; any vertex that can still be improved is either on or reachable from a negative-weight cycle. A BFS over the directed adjacency marks all vertices reachable from such flagged nodes. Finally, it prints per-vertex results: INF for unreachable, −INF for affected by negative cycles, and the finite shortest distance otherwise.

Time: O(VE) for relaxation plus O(V+E) for propagation, overall O(VE).Space: O(V+E) to store distances, edges, and adjacency.

Shortest path reconstruction when no negative cycle affects the target

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge { int u, v; long long w; };
5 
6 int main() {
7     ios::sync_with_stdio(false);
8     cin.tie(nullptr);
9 
10     int n, m, s, t; // source s, target t
11     if (!(cin >> n >> m >> s >> t)) {
12         cerr << "Usage: n m s t then m lines: u v w\n";
13         return 0;
14     }
15     vector<Edge> edges(m);
16     for (int i = 0; i < m; ++i) {
17         int u, v; long long w; cin >> u >> v >> w;
18         edges[i] = {u, v, w};
19     }
20 
21     const long long INF = (long long)4e18;
22     vector<long long> d(n, INF);
23     vector<int> parent(n, -1);
24     d[s] = 0;
25 
26     // V-1 relaxations with parent tracking
27     for (int i = 0; i < n - 1; ++i) {
28         bool any = false;
29         for (const auto &e : edges) {
30             if (d[e.u] == INF) continue;
31             long long cand = d[e.u] + e.w;
32             if (cand < d[e.v]) {
33                 d[e.v] = cand;
34                 parent[e.v] = e.u;
35                 any = true;
36             }
37         }
38         if (!any) break;
39     }
40 
41     // Check if target is affected by a negative cycle
42     vector<int> affected(n, 0);
43     for (const auto &e : edges) {
44         if (d[e.u] == INF) continue;
45         if (d[e.u] + e.w < d[e.v]) affected[e.v] = 1;
46     }
47     // If t is affected or can reach from affected, mark; build adjacency to propagate
48     vector<vector<int>> adj(n);
49     for (auto &e : edges) adj[e.u].push_back(e.v);
50     queue<int> q; vector<int> vis(n, 0);
51     for (int v = 0; v < n; ++v) if (affected[v]) { q.push(v); vis[v] = 1; }
52     while (!q.empty()) {
53         int u = q.front(); q.pop();
54         for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; q.push(v); }
55     }
56 
57     if (d[t] == INF) {
58         cout << "No path from s to t.\n";
59         return 0;
60     }
61     if (vis[t]) {
62         cout << "Shortest path to t is -INF due to a reachable negative cycle.\n";
63         return 0;
64     }
65 
66     // Reconstruct path s -> ... -> t using parent[]
67     vector<int> path;
68     for (int cur = t; cur != -1; cur = parent[cur]) path.push_back(cur);
69     reverse(path.begin(), path.end());
70 
71     // Sanity: ensure path starts with s
72     if (path.empty() || path[0] != s) {
73         cout << "No path from s to t.\n";
74         return 0;
75     }
76 
77     cout << "Distance: " << d[t] << "\nPath (" << path.size() << " vertices): ";
78     for (size_t i = 0; i < path.size(); ++i) cout << path[i] << (i+1==path.size()? '\n' : ' ');
79     return 0;
80 }
81

Tracks a predecessor for each vertex when a relaxation improves its distance. After standard Bellman–Ford, it checks and propagates negative-cycle effects. If the target is unaffected and reachable, it reconstructs the path by walking parent pointers backward from t to s and then reversing the sequence.

Time: O(VE) to compute distances and O(V+E) to propagate cycle effects.Space: O(V+E) for distances, parents, and graph structures.

Early-stopping Bellman–Ford (reporting the number of rounds used)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge { int u, v; long long w; };
5 
6 int main() {
7     ios::sync_with_stdio(false);
8     cin.tie(nullptr);
9 
10     int n, m, s; cin >> n >> m >> s;
11     vector<Edge> edges(m);
12     for (int i = 0; i < m; ++i) {
13         int u, v; long long w; cin >> u >> v >> w;
14         edges[i] = {u, v, w};
15     }
16 
17     const long long INF = (long long)4e18;
18     vector<long long> d(n, INF);
19     d[s] = 0;
20 
21     int rounds = 0;
22     for (int i = 0; i < n - 1; ++i) {
23         bool any = false;
24         for (const auto &e : edges) {
25             if (d[e.u] == INF) continue;
26             long long cand = d[e.u] + e.w;
27             if (cand < d[e.v]) { d[e.v] = cand; any = true; }
28         }
29         rounds++;
30         if (!any) break; // stop if nothing changed
31     }
32 
33     // Quick negative cycle check
34     bool neg = false;
35     for (const auto &e : edges) {
36         if (d[e.u] == INF) continue;
37         if (d[e.u] + e.w < d[e.v]) { neg = true; break; }
38     }
39 
40     cout << "Rounds used: " << rounds << "\n";
41     if (neg) cout << "Negative cycle reachable from source.\n";
42     else {
43         for (int v = 0; v < n; ++v) {
44             if (d[v] == INF) cout << "INF\n";
45             else cout << d[v] << "\n";
46         }
47     }
48     return 0;
49 }
50

Implements Bellman–Ford with an early exit when a full pass performs no updates. It also reports how many rounds were actually needed and checks for a reachable negative cycle. On graphs where shortest paths use few edges, this optimization can significantly reduce runtime in practice while preserving correctness.

Time: O(kE), where k ≤ V−1 is the number of rounds until stabilization; worst-case O(VE).Space: O(V+E).

Difference constraints feasibility with a super-source

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Solve constraints of the form x[v] - x[u] <= w(u,v)
5 // Build a graph with edge u -> v of weight w(u,v) and add a super-source 0 with 0-weight edges to all vertices.
6 // If a negative cycle is reachable from 0, the system is infeasible.
7 
8 struct Edge { int u, v; long long w; };
9 
10 int main() {
11     ios::sync_with_stdio(false);
12     cin.tie(nullptr);
13 
14     int n, m; // n variables (1..n), m constraints
15     cin >> n >> m;
16     vector<Edge> edges;
17     edges.reserve(m + n);
18 
19     for (int i = 0; i < m; ++i) {
20         int u, v; long long w; // x[v] - x[u] <= w
21         cin >> u >> v >> w;
22         edges.push_back({u, v, w});
23     }
24 
25     // Add super-source 0 -> i with 0 weight
26     for (int i = 1; i <= n; ++i) edges.push_back({0, i, 0});
27 
28     const long long INF = (long long)4e18;
29     vector<long long> d(n + 1, INF);
30     d[0] = 0;
31 
32     // Bellman-Ford on vertices {0..n}
33     for (int i = 0; i < n; ++i) { // (n) rounds suffice on n+1 vertices for feasibility
34         bool any = false;
35         for (auto &e : edges) {
36             if (d[e.u] == INF) continue;
37             long long cand = d[e.u] + e.w;
38             if (cand < d[e.v]) { d[e.v] = cand; any = true; }
39         }
40         if (!any) break;
41     }
42 
43     bool infeasible = false;
44     for (auto &e : edges) {
45         if (d[e.u] == INF) continue;
46         if (d[e.u] + e.w < d[e.v]) { infeasible = true; break; }
47     }
48 
49     if (infeasible) cout << "Infeasible (negative cycle detected).\n";
50     else {
51         cout << "Feasible. One solution (potentials):\n";
52         for (int i = 1; i <= n; ++i) cout << d[i] << (i==n?'\n':' ');
53     }
54     return 0;
55 }
56

Transforms each inequality x[v] − x[u] ≤ w into a directed edge u→v with weight w and adds a super-source 0 with 0-weight edges to all variables. Running Bellman–Ford from 0 checks feasibility: any reachable negative cycle violates the constraints. If feasible, the distances provide one valid assignment of variables (potentials) that satisfies all inequalities.

Time: O((n+1)(m+n)) = O(nm + n^2).Space: O(m+n).

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Edge {
5	int u, v; // from u to v
6	long long w; // weight
7	};
8
9	int main() {
10	ios::sync_with_stdio(false);
11	cin.tie(nullptr);
12
13	int n, m, s; // n vertices (0..n-1), m edges, source s
14	if (!(cin >> n >> m >> s)) {
15	cerr << "Usage: provide n m s followed by m edges (u v w)\n";
16	return 0;
17	}
18
19	vector<Edge> edges(m);
20	for (int i = 0; i < m; ++i) {
21	int u, v; long long w;
22	cin >> u >> v >> w;
23	edges[i] = {u, v, w};
24	}
25
26	const long long INF = (long long)4e18; // safe INF to avoid overflow on add
27	vector<long long> d(n, INF);
28	d[s] = 0;
29
30	// V-1 relaxation rounds
31	for (int i = 0; i < n - 1; ++i) {
32	bool any = false;
33	for (const auto &e : edges) {
34	if (d[e.u] == INF) continue; // unreachable source endpoint
35	if (d[e.v] > d[e.u] + e.w) {
36	d[e.v] = d[e.u] + e.w;
37	any = true;
38	}
39	}
40	if (!any) break; // early stopping optimization
41	}
42
43	// Build adjacency to propagate negative cycle reachability
44	vector<vector<int>> adj(n);
45	for (const auto &e : edges) adj[e.u].push_back(e.v);
46
47	// Find vertices whose distance can still be improved → on or after a reachable negative cycle
48	vector<int> bad(n, 0);
49	for (const auto &e : edges) {
50	if (d[e.u] == INF) continue;
51	if (d[e.v] > d[e.u] + e.w) {
52	bad[e.v] = 1;
53	}
54	}
55
56	// Propagate bad marks to everything reachable (they are effectively -INF)
57	queue<int> q;
58	vector<int> vis(n, 0);
59	for (int v = 0; v < n; ++v) if (bad[v]) { q.push(v); vis[v] = 1; }
60	while (!q.empty()) {
61	int u = q.front(); q.pop();
62	for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; q.push(v); }
63	}
64
65	// Output: if unreachable → INF; if vis[v] → -INF; else finite distance
66	for (int v = 0; v < n; ++v) {
67	if (d[v] == INF) {
68	cout << "INF\n";
69	} else if (vis[v]) {
70	cout << "-INF\n";
71	} else {
72	cout << d[v] << "\n";
73	}
74	}
75	return 0;
76	}
77

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Edge { int u, v; long long w; };
5
6	int main() {
7	ios::sync_with_stdio(false);
8	cin.tie(nullptr);
9
10	int n, m, s, t; // source s, target t
11	if (!(cin >> n >> m >> s >> t)) {
12	cerr << "Usage: n m s t then m lines: u v w\n";
13	return 0;
14	}
15	vector<Edge> edges(m);
16	for (int i = 0; i < m; ++i) {
17	int u, v; long long w; cin >> u >> v >> w;
18	edges[i] = {u, v, w};
19	}
20
21	const long long INF = (long long)4e18;
22	vector<long long> d(n, INF);
23	vector<int> parent(n, -1);
24	d[s] = 0;
25
26	// V-1 relaxations with parent tracking
27	for (int i = 0; i < n - 1; ++i) {
28	bool any = false;
29	for (const auto &e : edges) {
30	if (d[e.u] == INF) continue;
31	long long cand = d[e.u] + e.w;
32	if (cand < d[e.v]) {
33	d[e.v] = cand;
34	parent[e.v] = e.u;
35	any = true;
36	}
37	}
38	if (!any) break;
39	}
40
41	// Check if target is affected by a negative cycle
42	vector<int> affected(n, 0);
43	for (const auto &e : edges) {
44	if (d[e.u] == INF) continue;
45	if (d[e.u] + e.w < d[e.v]) affected[e.v] = 1;
46	}
47	// If t is affected or can reach from affected, mark; build adjacency to propagate
48	vector<vector<int>> adj(n);
49	for (auto &e : edges) adj[e.u].push_back(e.v);
50	queue<int> q; vector<int> vis(n, 0);
51	for (int v = 0; v < n; ++v) if (affected[v]) { q.push(v); vis[v] = 1; }
52	while (!q.empty()) {
53	int u = q.front(); q.pop();
54	for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; q.push(v); }
55	}
56
57	if (d[t] == INF) {
58	cout << "No path from s to t.\n";
59	return 0;
60	}
61	if (vis[t]) {
62	cout << "Shortest path to t is -INF due to a reachable negative cycle.\n";
63	return 0;
64	}
65
66	// Reconstruct path s -> ... -> t using parent[]
67	vector<int> path;
68	for (int cur = t; cur != -1; cur = parent[cur]) path.push_back(cur);
69	reverse(path.begin(), path.end());
70
71	// Sanity: ensure path starts with s
72	if (path.empty() \|\| path[0] != s) {
73	cout << "No path from s to t.\n";
74	return 0;
75	}
76
77	cout << "Distance: " << d[t] << "\nPath (" << path.size() << " vertices): ";
78	for (size_t i = 0; i < path.size(); ++i) cout << path[i] << (i+1==path.size()? '\n' : ' ');
79	return 0;
80	}
81

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Solve constraints of the form x[v] - x[u] <= w(u,v)
5	// Build a graph with edge u -> v of weight w(u,v) and add a super-source 0 with 0-weight edges to all vertices.
6	// If a negative cycle is reachable from 0, the system is infeasible.
7
8	struct Edge { int u, v; long long w; };
9
10	int main() {
11	ios::sync_with_stdio(false);
12	cin.tie(nullptr);
13
14	int n, m; // n variables (1..n), m constraints
15	cin >> n >> m;
16	vector<Edge> edges;
17	edges.reserve(m + n);
18
19	for (int i = 0; i < m; ++i) {
20	int u, v; long long w; // x[v] - x[u] <= w
21	cin >> u >> v >> w;
22	edges.push_back({u, v, w});
23	}
24
25	// Add super-source 0 -> i with 0 weight
26	for (int i = 1; i <= n; ++i) edges.push_back({0, i, 0});
27
28	const long long INF = (long long)4e18;
29	vector<long long> d(n + 1, INF);
30	d[0] = 0;
31
32	// Bellman-Ford on vertices {0..n}
33	for (int i = 0; i < n; ++i) { // (n) rounds suffice on n+1 vertices for feasibility
34	bool any = false;
35	for (auto &e : edges) {
36	if (d[e.u] == INF) continue;
37	long long cand = d[e.u] + e.w;
38	if (cand < d[e.v]) { d[e.v] = cand; any = true; }
39	}
40	if (!any) break;
41	}
42
43	bool infeasible = false;
44	for (auto &e : edges) {
45	if (d[e.u] == INF) continue;
46	if (d[e.u] + e.w < d[e.v]) { infeasible = true; break; }
47	}
48
49	if (infeasible) cout << "Infeasible (negative cycle detected).\n";
50	else {
51	cout << "Feasible. One solution (potentials):\n";
52	for (int i = 1; i <= n; ++i) cout << d[i] << (i==n?'\n':' ');
53	}
54	return 0;
55	}
56