Skip to content

Bellman-Ford

Bellman-Ford is the brute-force answer to shortest paths: relax every edge, repeat \(N - 1\) times, done. It's slower than Dijkstra by a factor of \(V\). But it handles negative edges, detects negative cycles, and its simplicity makes it nearly impossible to implement incorrectly. When Dijkstra can't be trusted, Bellman-Ford is the algorithm you reach for.

The Algorithm

Distance array values improving across Bellman-Ford rounds

Bellman-Ford relaxation rounds: distance array improves each round

The idea is embarrassingly simple. A shortest path visits at most \(N - 1\) edges (no repeated vertices in an optimal path without negative cycles). After \(k\) iterations of relaxing all edges, you've found all shortest paths that use at most \(k\) edges. After \(N - 1\) iterations, you've found them all.

struct Edge { int u, v; long long w; };
vector<Edge> edges; // all M edges

vector<long long> dist(n + 1, LLONG_MAX);
dist[1] = 0;

for (int i = 0; i < n - 1; i++)
    for (auto [u, v, w] : edges)
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v])
            dist[v] = dist[u] + w;

Time: \(O(VE)\). Space: \(O(V + E)\).

Key insight. After iteration \(k\), dist[v] holds the shortest path from source to \(v\) using at most \(k + 1\) edges. By iteration \(N - 1\), all paths (which have at most \(N - 1\) edges) are covered.

Full Trace

Graph with 4 nodes, source = 1:

1 --2--> 2 --(-3)--> 3 --2--> 4
1 --7--> 4

Edges: (1,2,2), (2,3,-3), (3,4,2), (1,4,7).

Iteration Edge relaxed dist[] before → after
1 (1,2,2) [0,∞,∞,∞] → [0,2,∞,∞]
1 (2,3,-3) [0,2,∞,∞] → [0,2,-1,∞]
1 (3,4,2) [0,2,-1,∞] → [0,2,-1,1]
1 (1,4,7) [0,2,-1,1] → [0,2,-1,1] (no change, 7>1)
2 all edges No changes — already converged
3 all edges No changes

Final: dist = [0, 2, -1, 1]. Path 1→2→3→4 costs \(2 + (-3) + 2 = 1\), beating the direct edge 1→4 (cost 7).

Gotcha. The if (dist[u] != LLONG_MAX) guard is essential. Without it, you'd compute LLONG_MAX + w, which overflows and produces garbage. Always check before relaxing.

Negative Cycle Detection

Negative cycle detection: cycle with total weight less than zero

After \(N - 1\) iterations, all shortest paths are finalized — unless a negative cycle exists. Run one more iteration (the \(N\)th). If any distance decreases, a negative cycle is reachable from the source.

// After N-1 iterations:
for (auto [u, v, w] : edges) {
    if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
        // Negative cycle detected!
    }
}

Why does this work? If no negative cycle exists, \(N - 1\) iterations are sufficient — every shortest path has at most \(N - 1\) edges. Any further improvement means a path with \(\geq N\) edges is shorter. That's only possible if the path revisits a node, forming a cycle. And that cycle must be negative (otherwise revisiting wouldn't improve the distance).

Trace: Negative Cycle Detection

Graph with 3 nodes, source = 1:

1 --1--> 2 --(-3)--> 3 --1--> 2 (cycle: 2→3→2, weight = -2)

Edges: (1,2,1), (2,3,-3), (3,2,1).

Iteration dist[] after all relaxations
1 [0, 1, -2]
2 [0, -1, -2] (dist[2] improved via 3→2: -2+1=-1)
3 (Nth) [0, -1, -4] (dist[3] improved: -1+(-3)=-4 < -2) → Negative cycle!

The distances keep decreasing because the cycle 2→3→2 has weight \((-3) + 1 = -2 < 0\).

CSES High Score

Problem: Directed weighted graph, \(N\) nodes, \(M\) edges. Find the longest path from 1 to \(N\). If you can make the score arbitrarily large (positive cycle on a 1-to-\(N\) path), print \(-1\).

Translation: Negate all weights. "Longest path" becomes "shortest path with negated weights." A positive cycle becomes a negative cycle. Use Bellman-Ford.

The catch: a negative cycle might exist somewhere in the graph but NOT on any path from 1 to \(N\). You need two reachability checks.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    struct Edge { int u, v; long long w; };
    vector<Edge> edges(m);
    vector<vector<int>> adj(n + 1), radj(n + 1);

    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].w = -edges[i].w;
        adj[edges[i].u].push_back(edges[i].v);
        radj[edges[i].v].push_back(edges[i].u);
    }

    // BFS from 1: which nodes are reachable from source?
    vector<bool> from1(n + 1, false);
    queue<int> q;
    q.push(1); from1[1] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (!from1[v]) { from1[v] = true; q.push(v); }
    }

    // BFS from N on reverse graph: which nodes can reach N?
    vector<bool> toN(n + 1, false);
    q.push(n); toN[n] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : radj[u])
            if (!toN[v]) { toN[v] = true; q.push(v); }
    }

    // Bellman-Ford
    vector<long long> dist(n + 1, LLONG_MAX);
    dist[1] = 0;
    for (int i = 0; i < n - 1; i++)
        for (auto [u, v, w] : edges)
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;

    // Nth iteration: negative cycle on path 1→N?
    for (auto [u, v, w] : edges) {
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
            if (from1[u] && toN[v]) {
                cout << -1 << "\n";
                return 0;
            }
        }
    }

    cout << -dist[n] << "\n";
}

Key insight. The problem isn't just "does a negative cycle exist?" It's "does a negative cycle sit on a path from 1 to \(N\)?" Always check both forward reachability (from source) and backward reachability (to destination).

CSES Cycle Finding

Problem: Given a directed graph, find a negative cycle and print its nodes. If none exists, print "NO."

Key differences from High Score: (1) the cycle can be anywhere, not just on a path from 1 to \(N\). (2) You must output the actual cycle nodes.

Approach:

  1. Initialize dist[v] = 0 for all nodes. This simulates a virtual source connected to every node with a zero-weight edge.
  2. Run \(N\) iterations of Bellman-Ford, tracking predecessors.
  3. If any edge relaxes on the \(N\)th iteration, node \(v\) is on or downstream of a negative cycle.
  4. Walk back through predecessors \(N\) times to land inside the cycle.
  5. Collect the cycle by following predecessors until you revisit a node.
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    struct Edge { int u, v; long long w; };
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;

    vector<long long> dist(n + 1, 0);
    vector<int> par(n + 1, -1);
    int cycle_node = -1;

    for (int i = 0; i < n; i++) {
        cycle_node = -1;
        for (auto [u, v, w] : edges) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                par[v] = u;
                if (i == n - 1) cycle_node = v;
            }
        }
    }

    if (cycle_node == -1) {
        cout << "NO\n";
    } else {
        int v = cycle_node;
        for (int i = 0; i < n; i++) v = par[v];

        vector<int> cycle;
        int u = v;
        do {
            cycle.push_back(u);
            u = par[u];
        } while (u != v);
        cycle.push_back(v);
        reverse(cycle.begin(), cycle.end());

        cout << "YES\n";
        for (int x : cycle) cout << x << " ";
        cout << "\n";
    }
}

Gotcha. Initialize all distances to 0, not infinity. You're looking for a negative cycle anywhere in the graph, not shortest paths from a specific source. Setting all distances to 0 simulates edges from a virtual source to every node with weight 0.

Why Walk Back N Times?

When the \(N\)th iteration finds a relaxable edge at node \(v\), that node might not be on the negative cycle itself — it might be downstream of one. Walking back \(N\) times through the predecessor chain guarantees you enter the cycle. Since the cycle has at most \(N\) nodes, \(N\) backward steps are enough.

Steps back Position
0 Node \(v\) (might be downstream)
1-k Walking toward the cycle
k+1 to N Inside the cycle, looping
N Guaranteed inside the cycle

Bellman-Ford vs Dijkstra

Dijkstra Bellman-Ford
Negative edges Fails Works
Negative cycle detection Cannot Can
Time complexity \(O((V+E) \log V)\) \(O(VE)\)
Practical speed Fast Slow
Implementation Priority queue Simple nested loop

For \(V = 2500\), \(E = 5000\): Dijkstra does ~85K operations. Bellman-Ford does ~12.5M. That's a ~150x difference. Use Dijkstra when all weights are non-negative.

abc137_e — Coins Respawn. Weighted directed graph. Each edge gives coins, but each step costs \(P\). Maximize profit from 1 to \(N\). If infinite profit is possible (positive cycle on a 1-to-\(N\) path), report it. Transform: edge weight becomes \(P - w_i\). Now it's the same structure as CSES High Score.

abc061_d — Score Attack. Longest path from 1 to \(N\), report \(-\infty\) if a positive cycle exists on the path. Same approach: negate weights, run Bellman-Ford, check for negative cycles on the 1-to-\(N\) path.

Exercises

  1. Edge order. Re-run the 4-node trace with edges in reverse order: (1,4,7), (3,4,2), (2,3,-3), (1,2,2). How many iterations until convergence?

  2. SPFA. The Shortest Path Faster Algorithm uses a queue: only relax edges from nodes whose distance just changed. What's its worst-case complexity? (Same as Bellman-Ford. But it's often faster in practice.)

  3. Multiple negative cycles. A graph has two negative cycles. Bellman-Ford's \(N\)th iteration detects at least one. Can it miss the other? Does it matter?

Problems

Problem Link Difficulty
CSES — High Score cses.fi/problemset/task/1673 Medium
CSES — Cycle Finding cses.fi/problemset/task/1197 Medium
AtCoder abc137_e — Coins Respawn atcoder.jp/contests/abc137/tasks/abc137_e Medium
AtCoder abc061_d — Score Attack atcoder.jp/contests/abc061/tasks/abc061_d Medium
LC 787 — Cheapest Flights Within K Stops leetcode.com/problems/cheapest-flights-within-k-stops Medium