Skip to content

Bellman-Ford

Shortest paths from one start even when some edges have negative weights. Relax every edge, \(V-1\) times. If a further round still improves something, there is a negative cycle and "shortest" makes no sense.

Time Extra space Handles Detects
\(O(VE)\) \(O(V)\) negative weights negative cycles reachable from the start

The idea

Negative weights appear naturally: a refund, an energy gain going downhill, a currency exchange rate turned into a logarithm. Dijkstra settles vertices for good and so cannot cope with them.

Bellman-Ford never settles anything. It just relaxes every edge (dist[v] = min(dist[v], dist[u] + w)), round after round. After round 1, every shortest path that uses at most 1 edge is correct; after round 2, every one with at most 2 edges; and so on. A shortest path never repeats a vertex (if there is no negative cycle), so it has at most \(V-1\) edges, and \(V-1\) rounds are enough.

If round \(V\) would still lower some distance, the only explanation is a negative cycle: going round it again and again lowers the cost forever. Bellman-Ford reports it instead of a wrong answer.

How it works

  1. dist[src] = 0, all others \(\infty\).
  2. Repeat \(V-1\) times: for every edge (u, v, w), if dist[u] + w < dist[v], lower dist[v]. Stop early if a round changes nothing.
  3. One more pass over the edges: if any distance can still be lowered, a negative cycle is reachable.

Code

INF = float("inf")


def bellman_ford(n, edges, src):
    """Shortest distances from src even with negative edge weights.
    Returns (dist, None) or (None, a vertex on a negative cycle) if some distance can drop forever."""
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):                   # a shortest path uses at most n-1 edges
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w        # relax every edge, again and again
                changed = True
        if not changed:
            break                            # nothing improved: we are done early
    for u, v, w in edges:                    # one more round: any improvement means a negative cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None, v
    return dist, None


def show(dist):
    return "[" + ", ".join("inf" if d == INF else str(d) for d in dist) + "]"


if __name__ == "__main__":
    edges = [(0, 1, 6), (0, 2, 7), (1, 2, 8), (1, 3, 5), (1, 4, -4), (2, 3, -3), (2, 4, 9), (3, 1, -2),
             (4, 0, 2), (4, 3, 7)]
    dist, _ = bellman_ford(5, edges, 0)
    print(show(dist))
    dist, _ = bellman_ford(6, edges, 0)      # vertex 5 has no edges: unreachable
    print(show(dist))
    bad = [(0, 1, 1), (1, 2, -1), (2, 1, -1), (2, 3, 1)]
    print(bellman_ford(4, bad, 0)[1] is not None)

import java.util.Arrays;

public class BellmanFord {
    static final long INF = Long.MAX_VALUE;

    /** Shortest distances from src even with negative edge weights, or null if a negative cycle is reachable. */
    static long[] bellmanFord(int n, int[][] edges, int src) {
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int round = 0; round < n - 1; round++) { // a shortest path uses at most n-1 edges
            boolean changed = false;
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] != INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
            }
            if (!changed) break;                      // nothing improved: we are done early
        }
        for (int[] e : edges)                         // one more round: any improvement means a negative cycle
            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
        return dist;
    }

    static String show(long[] dist) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < dist.length; i++) sb.append(i > 0 ? ", " : "").append(dist[i] == INF ? "inf" : String.valueOf(dist[i]));
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1, 6}, {0, 2, 7}, {1, 2, 8}, {1, 3, 5}, {1, 4, -4}, {2, 3, -3}, {2, 4, 9}, {3, 1, -2},
            {4, 0, 2}, {4, 3, 7}};
        System.out.println(show(bellmanFord(5, edges, 0)));
        System.out.println(show(bellmanFord(6, edges, 0)));   // vertex 5 has no edges: unreachable
        int[][] bad = {{0, 1, 1}, {1, 2, -1}, {2, 1, -1}, {2, 3, 1}};
        System.out.println(bellmanFord(4, bad, 0) == null ? "True" : "False");
    }
}

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

const long long INF = LLONG_MAX;
struct Edge { int u, v, w; };

// Shortest distances from src even with negative edge weights, or nothing if a negative cycle is reachable.
optional<vector<long long>> bellmanFord(int n, const vector<Edge>& edges, int src) {
    vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int round = 0; round < n - 1; round++) {    // a shortest path uses at most n-1 edges
        bool changed = false;
        for (auto& e : edges)
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) { dist[e.v] = dist[e.u] + e.w; changed = true; }
        if (!changed) break;                         // nothing improved: we are done early
    }
    for (auto& e : edges)                            // one more round: any improvement means a negative cycle
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) return nullopt;
    return dist;
}

void show(const vector<long long>& dist) {
    cout << "[";
    for (size_t i = 0; i < dist.size(); i++) {
        cout << (i ? ", " : "");
        if (dist[i] == INF) cout << "inf"; else cout << dist[i];
    }
    cout << "]\n";
}

int main() {
    vector<Edge> edges = {{0, 1, 6}, {0, 2, 7}, {1, 2, 8}, {1, 3, 5}, {1, 4, -4}, {2, 3, -3}, {2, 4, 9}, {3, 1, -2},
        {4, 0, 2}, {4, 3, 7}};
    show(*bellmanFord(5, edges, 0));
    show(*bellmanFord(6, edges, 0));                 // vertex 5 has no edges: unreachable
    vector<Edge> bad = {{0, 1, 1}, {1, 2, -1}, {2, 1, -1}, {2, 3, 1}};
    cout << (bellmanFord(4, bad, 0) ? "False" : "True") << "\n";
}

Output: [0, 2, 7, 4, -2], the same with inf for an extra unreachable vertex, and True: the graph with the cycle 1 → 2 → 1 of total weight \(-2\) has a negative cycle.

When to use it

  • Graphs with negative weights and few vertices or edges.
  • Detecting negative cycles: currency arbitrage (with weights \(-\log(\text{rate})\), a negative cycle is a sequence of trades that makes money), inconsistent constraints.
  • Difference constraints \(x_v - x_u \le w\): a system is solvable exactly when its constraint graph has no negative cycle, and Bellman-Ford finds a solution.
  • Distance-vector routing (RIP): each router relaxes its neighbours' tables, a distributed Bellman-Ford.
  • For non-negative weights, Dijkstra is much faster.

Common mistakes

  • Relaxing from \(\infty\): INF + (-4) is not \(\infty\); check dist[u] != INF first (and in Java and C++, avoid overflow).
  • Only \(V-2\) rounds, or forgetting the final check.
  • Undirected graphs with a negative edge: the edge is itself a negative cycle (\(u \to v \to u\)).
  • Negative cycles that cannot be reached from the start do not affect its distances and are not reported.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: the demo graph from vertex 0

Edges in the order relaxed: 0→1 (6), 0→2 (7), 1→2 (8), 1→3 (5), 1→4 (−4), 2→3 (−3), 2→4 (9), 3→1 (−2), 4→0 (2), 4→3 (7).

Round Changes, in order Distances after (0..4)
1 d1 = 6, d2 = 7, d3 = 11, d4 = 2, d3 = 7 − 3 = 4, d1 = 4 − 2 = 2 0, 2, 7, 4, 2
2 d4 = 2 − 4 = −2 0, 2, 7, 4, −2
3 none: stop early 0, 2, 7, 4, −2

The order of edges matters for speed (round 1 already did a lot) but not for the final answer.

The math: why V − 1 rounds are enough

Lemma. After round \(k\), \(\text{dist}[v] \le\) the length of the shortest path from \(s\) to \(v\) that uses at most \(k\) edges. Proof by induction on \(k\): such a path is a path of at most \(k-1\) edges to some \(u\), then the edge \(u \to v\); after round \(k-1\), \(\text{dist}[u]\) is at most the first part, and round \(k\) relaxes \(u \to v\).

Also \(\text{dist}[v]\) is always the length of some real path, so it never drops below \(\delta(v)\).

No negative cycle reachable: a shortest path can drop any cycle (of weight \(\ge 0\)) without getting longer, so some shortest path is simple and has at most \(V-1\) edges. After \(V-1\) rounds, \(\text{dist}[v] = \delta(v)\), and no edge can be relaxed any more.

A negative cycle \(v_0 \to v_1 \to \cdots \to v_k = v_0\) reachable: suppose no edge could be relaxed, so \(\text{dist}[v_i] \le \text{dist}[v_{i-1}] + w(v_{i-1}, v_i)\) for every \(i\). Adding these \(k\) inequalities, the distances cancel (each appears once on each side) and

\[ 0 \;\le\; \sum_{i=1}^{k} w(v_{i-1}, v_i) \;<\; 0, \]

a contradiction. So round \(V\) always finds something to relax.

Time: \(V-1\) rounds of \(E\) relaxations: \(O(VE)\). The SPFA variant only re-relaxes edges out of vertices whose distance just changed; often much faster, but still \(O(VE)\) in the worst case.

Watch it step by step

Each frame is one full round over the edges; red edges and vertices changed in that round.

Variations and related ideas
  • Finding the negative cycle itself: take a vertex relaxed in round \(V\), follow parents \(V\) times to land inside the cycle, then walk the parents round it.
  • Shortest paths with at most \(k\) edges (cheapest flight with at most \(k\) stops): run exactly \(k\) rounds, relaxing from a copy of the previous round's distances.
  • Johnson's algorithm uses one Bellman-Ford run to reweight edges so that they are all non-negative, then runs Dijkstra from every vertex.

See also

References

  • R. Bellman, "On a routing problem", Quarterly of Applied Mathematics 16, 1958.
  • L. R. Ford Jr., Network Flow Theory, RAND Corporation paper P-923, 1956.
  • T. H. Cormen et al., Introduction to Algorithms, 4th ed., §22.1 (the Bellman-Ford algorithm); the demo graph is the one in their Bellman-Ford example.