I. In-Class Exercises

Programming Exercises

1. Negative Cycle (Bellman-Ford): L49986

II. Knowledge Summary

✨ Core Concept

The Bellman-Ford algorithm solves the single-source shortest path problem for graphs with negative edge weights. Unlike Dijkstra, it does not require non-negative edge weights and can detect negative weight cycles (negative cycles).

Core idea: Perform $V-1$ rounds of relaxation over all edges. After round $k$, the shortest paths using at most $k$ edges are guaranteed to be correctly computed. Since a shortest path has at most $V-1$ edges (no cycles), all shortest paths are found after $V-1$ rounds.

✨ Algorithm Principle

1. Initialize: dist[s] = 0, all other dist[v] = ∞.
2. Relax for $V-1$ rounds: In each round, iterate over all edges $(u, v, w)$ and relax:
   复制

   if dist[u] + w < dist[v]:
       dist[v] = dist[u] + w

3. Detect negative cycles: In round $V$, iterate over all edges again. If any edge can still be relaxed, the graph contains a negative weight cycle reachable from the source.

Why are $V-1$ rounds sufficient?

A shortest path does not contain cycles (positive cycles are wasteful, negative cycles make the shortest path undefined). A cycle-free path has at most $V-1$ edges. Round $i$ of relaxation guarantees that "shortest paths using $\leq i$ edges" are correctly computed. Therefore, after $V-1$ rounds, all shortest paths are computed.

What is a negative weight cycle?

If the graph contains a cycle whose total edge weight sum is negative, one can walk this cycle infinitely to keep reducing the path length. In this case, the shortest path does not exist (it is $-\infty$).

✨ Code Implementation

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 10005;
5const int MAXM = 50005;
6const long long INF = 1e18;
7
8struct Edge {
9    int u, v;
10    long long w;
11};
12
13Edge edges[MAXM]; // edge list array
14long long dist[MAXN];
15int n, m, s;
16
17bool bellmanFord(int s) {
18    // initialization
19    for (int i = 1; i <= n; i++) dist[i] = INF;
20    dist[s] = 0;
21
22    // perform n-1 rounds of relaxation
23    for (int i = 1; i <= n - 1; i++) {
24        bool updated = false; // optimization: terminate early if no updates
25        for (int j = 0; j < m; j++) {
26            int u = edges[j].u, v = edges[j].v;
27            long long w = edges[j].w;
28            if (dist[u] != INF && dist[u] + w < dist[v]) {
29                dist[v] = dist[u] + w;
30                updated = true;
31            }
32        }
33        if (!updated) break; // early convergence
34    }
35
36    // round n: detect negative cycle
37    for (int j = 0; j < m; j++) {
38        int u = edges[j].u, v = edges[j].v;
39        long long w = edges[j].w;
40        if (dist[u] != INF && dist[u] + w < dist[v]) {
41            return false; // negative cycle exists
42        }
43    }
44
45    return true; // no negative cycle
46}
47
48int main() {
49    ios::sync_with_stdio(false);
50    cin.tie(nullptr);
51
52    cin >> n >> m >> s;
53    for (int i = 0; i < m; i++) {
54        cin >> edges[i].u >> edges[i].v >> edges[i].w;
55    }
56
57    if (bellmanFord(s)) {
58        for (int i = 1; i <= n; i++) {
59            if (dist[i] == INF)
60                cout << "unreachable";
61            else
62                cout << dist[i];
63            if (i < n) cout << " ";
64        }
65        cout << endl;
66    } else {
67        cout << "NEGATIVE CYCLE" << endl;
68    }
69
70    return 0;
71}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 10005;
5const int MAXM = 50005;
6const long long INF = 1e18;
7
8struct Edge { int u, v; long long w; };
9
10Edge edges[MAXM];
11long long dist[MAXN];
12int pre[MAXN]; // predecessor node
13int n, m;
14
15// find a node on the negative cycle and output the cycle
16void findNegativeCycle() {
17    for (int i = 1; i <= n; i++) dist[i] = 0; // initialize all to 0
18    fill(pre, pre + n + 1, -1);
19
20    int lastUpdated = -1;
21    for (int i = 1; i <= n; i++) {
22        lastUpdated = -1;
23        for (int j = 0; j < m; j++) {
24            int u = edges[j].u, v = edges[j].v;
25            long long w = edges[j].w;
26            if (dist[u] + w < dist[v]) {
27                dist[v] = dist[u] + w;
28                pre[v] = u;
29                lastUpdated = v;
30            }
31        }
32    }
33
34    if (lastUpdated == -1) {
35        cout << "NO NEGATIVE CYCLE" << endl;
36        return;
37    }
38
39    // trace back n steps from lastUpdated to ensure we are on the cycle
40    int x = lastUpdated;
41    for (int i = 0; i < n; i++) x = pre[x];
42
43    // output the cycle
44    cout << "Negative cycle: ";
45    int cur = x;
46    do {
47        cout << cur << " -> ";
48        cur = pre[cur];
49    } while (cur != x);
50    cout << x << endl;
51}

✨ Execution Example

Graph: 4 vertices, 5 edges, source $s = 1$.

Round 2 has no updates, terminate early. Shortest paths:

• $1 \to 2$: 1
• $1 \to 3$: 3 (via 1→2→3)
• $1 \to 4$: -4 (via 1→2→4, because of negative edge 2→4=-5)

Round 4 (negative cycle detection): no edge can be relaxed, no negative cycle exists.

✨ Step-by-Step Solution Guide

1. Determine if Bellman-Ford is needed:

   • Negative edge weights → must use Bellman-Ford (or SPFA).
   • Need to detect negative cycles → use Bellman-Ford.
   • No negative edge weights → prefer Dijkstra (faster).

2. Choose graph representation: Bellman-Ford iterates over all edges, so an edge list array is most convenient.

3. Optimization techniques:

   • Early termination: If no updates occur in a round, convergence is reached; break out.
   • Limit edges in shortest path: If the problem limits the path to at most $k$ edges, only relax for $k$ rounds.

4. Scope of negative cycle detection:

   • Standard Bellman-Ford only detects negative cycles reachable from the source.
   • To detect all negative cycles in the graph, initialize all vertex distances to 0.

✨ Common Mistakes

1. Wrong number of relaxation rounds: Should relax for $V-1$ rounds (not $V$ or $E$ rounds).
2. Not checking dist[u] != INF: Unreachable vertices from the source should not participate in relaxation; otherwise INF + w may overflow.
3. Undirected graph edge count doubling: Each undirected edge is stored twice; the edge array size should be $2M$.
4. Missing negative cycle detection: Forgetting round $V$ detection leads to incorrect output when negative cycles exist.
5. Confusing with Dijkstra: Bellman-Ford has no vis array and is not a greedy algorithm.
6. Early termination optimization failure: This only optimizes constants; worst case still requires $V-1$ rounds.

✨ Algorithm Evaluation

Bellman-Ford is the foundational algorithm for handling negative edge weights. Although its time complexity is high, its simple logic and easy-to-prove correctness make it the prerequisite for understanding optimization algorithms like SPFA.

III. Homework

Programming Exercises

1. Messenger: T1376