Bellman–Ford algorithm

The Bellman–Ford algorithm finds the shortest distance from one vertex to every other vertex of a directed graph, even when some edges have negative weights. It also detects negative cycles, around which the distances keep dropping forever. If no weight is negative, Dijkstra's algorithm gives the same answers in O((n + m) \log m) instead of $O(nm)$.

Explanation

A game level has 4 rooms joined by one-way passages. Walking through a passage costs coins. Some passages have a chest on the way: the one from room 3 to room 2 holds more coins than the walk costs, so taking it earns 2 coins, and its cost is −2. How few coins do we need to spend to get from room 1 to room 4?

Fig. 1. The red route costs 4, the blue route 3.

The red route through room 2 costs 2 + 2 = 4. The blue route first goes to room 3, which costs more, but then the chest pays back the detour: 3 − 2 + 2 = 3. So we can't take the cheapest room first and treat its number as final, as Dijkstra's algorithm does. Dijkstra would settle room 2 at 2, because 2 is less than 3, but the route through the more expensive room 3 later brings it down to 1.

Instead, let's write next to each room the fewest coins found so far, 0 for room 1, and go through the rooms in a fixed order. From each room, try every passage out of it: if it reaches the next room for fewer coins than the number written there, replace the number. This is called relaxing the passage.

One pass over all the rooms is a round. After a round, start over, until a whole round changes nothing: then no number can get smaller, and every number is the cheapest.

Room 1 gets 0, and every other room has no number yet. Round 1 begins.

Round 1, room 1: the passage to room 2 gives 0 + 2 = 2, and room 2 gets its first number.

Round 1, room 1: the passage to room 3 gives 0 + 3 = 3, and room 3 gets its first number.

Round 1, room 2: the passage to room 4 gives 2 + 2 = 4, and room 4 gets its first number.

Round 1, room 3: the passage to room 2 gives 3 − 2 = 1, less than 2, so room 2 drops to 1.

Round 2, room 1: the passage to room 2 gives 0 + 2 = 2, no better than 1. Nothing changes.

Round 2, room 1: the passage to room 3 gives 0 + 3 = 3, no better than 3. Nothing changes.

Round 2, room 2: the passage to room 4 gives 1 + 2 = 3, less than 4, so room 4 drops to 3.

Round 2, room 3: the passage to room 2 gives 3 − 2 = 1, no better than 1. Nothing changes.

Round 3, room 1: the passage to room 2 gives 0 + 2 = 2, no better than 1. Nothing changes.

Round 3, room 1: the passage to room 3 gives 0 + 3 = 3, no better than 3. Nothing changes.

Round 3, room 2: the passage to room 4 gives 1 + 2 = 3, no better than 3. Nothing changes.

Round 3, room 3: the passage to room 2 gives 3 − 2 = 1, no better than 1. Nothing changes.

Round 3 changed nothing, so the run stops. Rooms 1 to 4 have 0, 1, 3 and 3.

1/14

Fig. 2. Step through three rounds on the small level. The ringed room is the one being taken, a blue arrow lowers a number and a grey arrow changes nothing. The box below shows the round.

In round 1, room 2 passes 2 + 2 = 4 on to room 4 before room 3 lowers room 2 to 3 − 2 = 1. Round 2 passes the new number on, and room 4 gets 3. Round 3 changes nothing, so we stop.

A bigger level has 6 rooms and 8 passages. The chest is on the passage from room 5 back to room 2. We look for the cheapest route from room 1 to room 6.

Fig. 3. Find the cheapest route from room 1 to room 6.

The red route costs 6. The blue route goes through rooms 3 and 5, takes the chest back to room 2, and then goes through room 4. It costs 1 + 2 − 3 + 2 + 2 = 4 and uses 5 passages. Each round goes through the rooms in order 1 to 6, and round 1 gives room 6 the number 6 along the red route.

Room 1 gets 0, and every other room has no number yet. Round 1 begins.

Round 1, room 1: the passage to room 2 gives 0 + 2 = 2, and room 2 gets its first number.

Round 1, room 1: the passage to room 3 gives 0 + 1 = 1, and room 3 gets its first number.

Round 1, room 2: the passage to room 4 gives 2 + 2 = 4, and room 4 gets its first number.

Round 1, room 3: the passage to room 5 gives 1 + 2 = 3, and room 5 gets its first number.

Round 1, room 4: the passage to room 5 gives 4 + 2 = 6, no better than 3. Nothing changes.

Round 1, room 4: the passage to room 6 gives 4 + 2 = 6, and room 6 gets its first number.

Round 1, room 5: the passage to room 2 gives 3 − 3 = 0, less than 2, so room 2 drops to 0.

Round 1, room 5: the passage to room 6 gives 3 + 7 = 10, no better than 6. Nothing changes.

Round 2, room 1: the passage to room 2 gives 0 + 2 = 2, no better than 0. Nothing changes.

Round 2, room 1: the passage to room 3 gives 0 + 1 = 1, no better than 1. Nothing changes.

Round 2, room 2: the passage to room 4 gives 0 + 2 = 2, less than 4, so room 4 drops to 2.

Round 2, room 3: the passage to room 5 gives 1 + 2 = 3, no better than 3. Nothing changes.

Round 2, room 4: the passage to room 5 gives 2 + 2 = 4, no better than 3. Nothing changes.

Round 2, room 4: the passage to room 6 gives 2 + 2 = 4, less than 6, so room 6 drops to 4.

Round 2, room 5: the passage to room 2 gives 3 − 3 = 0, no better than 0. Nothing changes.

Round 2, room 5: the passage to room 6 gives 3 + 7 = 10, no better than 4. Nothing changes.

Round 3, room 1: the passage to room 2 gives 0 + 2 = 2, no better than 0. Nothing changes.

Round 3, room 1: the passage to room 3 gives 0 + 1 = 1, no better than 1. Nothing changes.

Round 3, room 2: the passage to room 4 gives 0 + 2 = 2, no better than 2. Nothing changes.

Round 3, room 3: the passage to room 5 gives 1 + 2 = 3, no better than 3. Nothing changes.

Round 3, room 4: the passage to room 5 gives 2 + 2 = 4, no better than 3. Nothing changes.

Round 3, room 4: the passage to room 6 gives 2 + 2 = 4, no better than 4. Nothing changes.

Round 3, room 5: the passage to room 2 gives 3 − 3 = 0, no better than 0. Nothing changes.

Round 3, room 5: the passage to room 6 gives 3 + 7 = 10, no better than 4. Nothing changes.

Round 3 changed nothing, so the run stops. Rooms 1 to 6 have 0, 0, 1, 2, 3 and 4.

1/26

Fig. 4. Step through Bellman–Ford on the bigger level. The ringed room is the one being taken, a blue arrow lowers a number and a grey arrow changes nothing. The box below shows the round.

The run gives 0, 0, 1, 2, 3 and 4 coins for rooms 1 to 6, in 3 rounds.

With the rooms in another order it can take more rounds. In the order 6, 4, 2, 5, 3, 1, round 1 gives room 3 its final number, round 2 gives room 5 its final number, and only round 5 reaches room 6. The right number moves one passage along the blue route per round.

Fig. 5. The rooms taken in the order shown below. The number on a blue passage is the round that gives its end the correct number: round $k$ fixes exactly the end of the $k$-th passage of the blue route.

No order is slower: each round moves the right number at least one passage further along the cheapest route. A cheapest route never goes through a room twice, because going around a loop costs coins, as long as no loop earns them. So on a level with $n$ rooms it has at most n - 1 passages, and n - 1 rounds are always enough. The blue route has 5 passages, the most 6 rooms allow.

This is the Bellman–Ford algorithm: write 0 at the start, then relax every passage, round after round, until a round changes nothing. Without negative cycles that takes at most n - 1 rounds.

Negative cycles

Let the chest on the passage from room 5 to room 2 give 5 coins more than the walk, so its cost is −5. The loop from room 2 through rooms 4 and 5 and back to 2 costs 2 + 2 − 5 = −1: every trip around it earns a coin. A cycle whose costs add up to less than zero is a negative cycle. Every trip around it makes the rooms on it, and the rooms after it, 1 coin cheaper. Repeating rounds until nothing changes would never end here: room 6 gets 6 in round 1, then 2, 1, 0, −1, −2 and so on.

So the algorithm stops after n - 1 rounds, round 5 here, and runs one more, the check round. Without a negative cycle it would change nothing. Here it still lowers rooms 2, 4, 5 and 6 (Fig. 6), and these rooms have no cheapest route at all.

Fig. 6. The red cycle costs −1 per trip.

The rooms without a cheapest route are exactly those that can be reached from a negative cycle. The check round lowers at least one room on every negative cycle that can be reached from the start, but it can miss rooms after the cycle. In Fig. 7, the cycle between rooms 2 and 3 costs −1 and has a passage of cost 0 on to room 4. Room 4 also has a passage of cost 0 straight from the start, so it has 0 from round 1 on, and the check round, round 4, lowers only rooms 2 and 3. To find all such rooms, run a DFS along the passages from every room that changed in the check round, and mark every room it reaches. This takes O(n + m). Here the DFS from rooms 2 and 3 also marks room 4.

Fig. 7. Room 4 never changes, yet it has no cheapest route.

Implementation

In the code, rooms are vertices, passages are directed edges from u to v, and a passage's cost is the edge's weight w. The cost of the cheapest route is the shortest distance, and the number next to room v is d[v], the shortest distance from the start, vertex 1, to v found so far. A round only goes through all the edges, so the edges are kept in a plain array of triples (u, v, w), in input order.

1. Initialise: d[1] = 0, every other d[v] = INF.

2. Relax every edge: a round goes through all the edges in a fixed order. The code takes them in input order; the main example lists them by their start vertex, which is the order of the explanation. For an edge from u to v of weight w with d[u] != INF, if d[u] + w < d[v], set d[v] = d[u] + w and remember u as the parent of v: parent[v] = u.

3. Stop after a round that changes nothing, or after n - 1 rounds.

4. Check for a negative cycle: run the check round, round $n$. If it changes some d[v], a negative cycle can be reached from vertex 1.

The program reads n and m, then m lines u v w: a one-way edge from u to v of weight w. The start is vertex 1. If the check round changes some d[v], it prints negative cycle and, on a second line, the vertices of one negative cycle. Otherwise it prints the shortest distance to each vertex, with * for a vertex that can't be reached, since −1 is a valid distance here. For the main level the input is:

6 8
1 2 2
1 3 1
2 4 2
3 5 2
4 5 2
4 6 2
5 2 -3
5 6 7

d and parent are indexed by vertex from 1 to n, and the comments name the steps above.

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

const long long INF = 99;   // small for the demo; use LLONG_MAX for real inputs

struct Edge {
    int u, v;
    long long w;
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (auto& e : edges) cin >> e.u >> e.v >> e.w;

    // initialise
    vector<long long> d(n + 1, INF);
    vector<int> parent(n + 1, 0);
    d[1] = 0;

    // relax every edge, at most n - 1 rounds
    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;
        for (auto [u, v, w] : edges) {
            if (d[u] != INF && d[u] + w < d[v]) {
                d[v] = d[u] + w;
                parent[v] = u;
                changed = true;
            }
        }
        if (!changed) break;   // stop: a round changed nothing
    }

    // check for a negative cycle: round n
    int x = 0;
    for (auto [u, v, w] : edges) {
        if (d[u] != INF && d[u] + w < d[v]) {
            d[v] = d[u] + w;
            parent[v] = u;
            x = v;
        }
    }
    if (x != 0) {
        cout << "negative cycle\n";
        // print the cycle; remove this block if you only need to know there is one
        for (int i = 0; i < n; i++) x = parent[x];   // now x is on the cycle
        vector<int> cycle = {x};
        for (int v = parent[x]; v != x; v = parent[v]) cycle.push_back(v);
        cycle.push_back(x);
        reverse(cycle.begin(), cycle.end());
        for (int v : cycle) cout << v << ' ';
        cout << '\n';
        return 0;
    }

    for (int v = 1; v <= n; v++) {
        if (d[v] == INF) cout << '*';
        else cout << d[v];
        cout << (v < n ? ' ' : '\n');
    }
}

For an undirected graph, store each edge in both directions. A negative undirected edge between u and v is then a negative cycle by itself: going there and back has length 2w < 0.

Each round goes through m edges and there are at most n rounds, so the time is $O(nm)$ and the memory is O(n + m). For n = m = 10^4 that is about 10^8 relaxations, fine by the rough rule of thumb of 10^8 simple steps per second, but for n = 10^5 and m = 2 \cdot 10^5 it is 2 \cdot 10^{10}, too slow, so if no edge is negative, use Dijkstra.

Finding the cycle

To print a negative cycle, the program's check round also updates d and parent, and remembers the last vertex x it changed. A changed vertex may lie after the cycle rather than on it. So the program walks back along parent from x for n steps. From there, it walks back once more around the cycle, collecting the vertices, and reverses them.

On the level with −5, with the edge 4 \to 6 moved to the end of the input, the check round changes vertex 6 last, so x = 6, which is not on the cycle. The walk back goes from 6 to 4 and then around the cycle through 2, 5, 4, 2 and stops at 5 after 6 steps, and the second line is 5 2 4 5.

Why $n$ steps land on a negative cycle: each d_v was set from its parent's value plus the edge's weight, and the parent's value can only have dropped since, so d_v \ge d_p + w for the parent $p$. If the walk back from $x$ reached the start without repeating a vertex, adding these inequalities would make d_x at least the length of a path with at most n - 1 edges. But after round $k$, d_v is at most the length of the shortest path with at most $k$ edges (see the correctness proof), so d_x was already at most that length after round n - 1, and the check round lowered it. So the walk never reaches the start, and after $n$ steps it has visited n + 1 vertices: it is going around a cycle of parent edges. Adding the same inequalities around this cycle gives a total weight of at most 0, and the edge of the cycle that was set last makes the inequality strict, so the cycle is negative.

Some problems ask whether there is a negative cycle anywhere in the graph, not only one reachable from vertex 1. For them, start with every d[v] = 0, as if a new vertex had an edge of weight 0 to every vertex. Then every cycle can be reached. On the level with −5 this finds the cycle 2 4 5 2.

Paths with at most $k$ edges

Some problems limit the number of edges, such as "at most $k$ flights" (problem 4456). It is tempting to run $k$ rounds, but a round updates d in place and can carry a value along several edges at once. On the main level, round 1 already sets d[2] = 0 along the path through vertices 3 and 5, which has 3 edges, while the shortest distance with at most 1 edge is 2. To move exactly one edge per round, relax from a copy of the previous round's values:

for (int round = 1; round <= k; round++) {
    vector<long long> prev = d;
    for (auto [u, v, w] : edges) {
        if (prev[u] != INF && prev[u] + w < d[v]) {
            d[v] = prev[u] + w;
        }
    }
}

Now after round k, d[v] is the shortest distance using at most k edges. On the main level, vertex 6 gets $\infty$, $\infty$, 6, 6 and 4 for at most 1, 2, 3, 4 and 5 edges.

Correctness proof

Every finite d_v is the length of some path from $s$ to $v$, because it was set by a relaxation along a real edge. So d_v is never below the shortest distance. The algorithm keeps this invariant: after round $k$, d_v is at most the length of the shortest path from $s$ to $v$ with at most $k$ edges.

After round 0 it holds, because only $s$ can be reached with 0 edges. Suppose it holds after round k - 1. Take the shortest path to $v$ with at most $k$ edges, and let u \to v be its last edge, of weight $w$. The part up to $u$ has at most k - 1 edges, so after round k - 1, d_u is at most its length. During round $k$, d_u can only get smaller, and when the edge u \to v is relaxed, d_v becomes at most d_u + w. So after round $k$, d_v is at most the length of the path, whatever the order of the edges. In Fig. 5, this is the $k$-th edge of the blue path in round $k$.

If no negative cycle can be reached from $s$, a shortest path has at most n - 1 edges. So after round n - 1 every d_v equals the shortest distance, and the check round changes nothing. A round that changes nothing leaves the same values for the next round, so stopping early is safe.

Now suppose a negative cycle c_1 \to c_2 \to \dots \to c_k \to c_1 can be reached from $s$. After round n - 1 all its vertices have finite values. If the check round changed none of them, then no edge of the cycle could lower its end: d_{c_{i+1}} \le d_{c_i} + w_i for every edge of the cycle, with c_{k+1} = c_1. Adding these $k$ inequalities, every $d$ appears once on each side, which leaves 0 \le w_1 + \dots + w_k. That contradicts the cycle being negative. So the check round changes some d_v on every reachable negative cycle.

Common mistakes

• Relaxing from a vertex that hasn't been reached, so INF plus a negative weight looks like a real distance, and LLONG_MAX plus a positive weight overflows. Skip edges whose start has d_u = \infty.

• Looking for a negative cycle only from vertex 1 when the problem asks about the whole graph, which misses cycles that can't be reached from vertex 1. Start with every d_v = 0.

Similar algorithms

Dijkstra's algorithm also relaxes edges, but each one only once, from the vertex closest to the start among those not taken yet. That order is correct only when no weight is negative; the Dijkstra article shows a negative edge that breaks it. Without negative weights Dijkstra is faster, O((n + m) \log m).

SPFA is Bellman–Ford with a queue. It re-checks only the edges out of vertices whose distance has just changed. Its worst case is still $O(nm)$.

Floyd–Warshall finds the shortest distances between all pairs of vertices in O(n^3), and allows negative edges. A negative d_{ii} means a negative cycle through $i$. For $n$ up to a few hundred, with the graph given as a table, it is an alternative to Bellman–Ford.

If the graph has no cycles at all, one round with the vertices taken in topological order is enough. It runs in O(n + m) and finds shortest and longest paths alike.

Practice