Bellman-Ford

Why it exists

Dijkstra's algorithm fails as soon as one edge weight is negative, yet negative weights are natural: a gain, a refund, a rebate, the logarithm of an exchange rate. Bellman-Ford handles them. It is slower, $\Theta(VE)$, because it is simple and cautious: it relaxes every edge again and again until nothing improves. It also answers a question Dijkstra cannot: is there a negative cycle (a cycle of negative total weight), in which case shortest paths do not exist because one can go round and round to get ever cheaper? GATE asks for the distances after a given number of passes, the number of passes needed, the running time, and negative cycle detection.

Prerequisites

You need relaxation, shortest-path distance and Dijkstra's algorithm (Dijkstra).

Precise definitions

Negative cycle. A directed cycle whose edge weights sum to less than $0$. If one is reachable from the source and can reach a vertex $v$, then $\delta(s, v) = -\infty$ (there is no shortest path to $v$). If there is no negative cycle on any path from $s$, shortest paths exist, are simple (no repeated vertex, so they have at most $V - 1$ edges), even with negative edges.

Bellman-Ford algorithm. $\text{dist}[s] = 0$, all others $\infty$. Repeat $V - 1$ times a pass: relax every edge $u \to v$ of the graph once (in any fixed order). Then do one more pass without changing anything: if some edge can still be relaxed, a negative cycle is reachable from $s$; otherwise the distances are the shortest-path distances. A pass in which nothing changes lets the algorithm stop early: nothing will change in later passes either.

Walk. A path that may repeat vertices. Relaxation passes compute the best walk with at most a given number of edges.

How it works

The animation runs the real code on five vertices and the edge list $0 \to 1\,(5)$, $0 \to 2\,(4)$, $1 \to 3\,(3)$, $2 \to 1\,(-2)$, $2 \to 3\,(6)$, $3 \to 4\,(2)$, $1 \to 4\,(9)$. Every edge is examined in each pass; the relaxed ones are marked.

The program below runs the same algorithm and prints the distances after each pass. It is then run on a second graph in which the edge $4 \to 1$ of weight $-8$ has been added.

#include <stdio.h>
 
#define N 5
#define INF 1000000
 
struct edge { int u, v, w; };
 
static void show(const int dist[]) {
    for (int v = 0; v < N; v++) {
        if (dist[v] >= INF) printf(" inf");
        else printf(" %3d", dist[v]);
    }
}
 
/* returns 1 if a negative cycle is reachable from src */
static int bellman_ford(const struct edge e[], int m, int src, int dist[], int verbose) {
    for (int v = 0; v < N; v++) dist[v] = INF;
    dist[src] = 0;
    for (int pass = 1; pass <= N - 1; pass++) {
        int changed = 0;
        for (int i = 0; i < m; i++) {
            if (dist[e[i].u] < INF && dist[e[i].u] + e[i].w < dist[e[i].v]) {
                dist[e[i].v] = dist[e[i].u] + e[i].w;
                changed = 1;
            }
        }
        if (verbose) { printf("pass %d:", pass); show(dist); printf("%s\n", changed ? "" : "   (no change: stop)"); }
        if (!changed) break;
    }
    for (int i = 0; i < m; i++)
        if (dist[e[i].u] < INF && dist[e[i].u] + e[i].w < dist[e[i].v]) return 1;
    return 0;
}
 
int main(void) {
    struct edge e[7] = {{0, 1, 5}, {0, 2, 4}, {1, 3, 3}, {2, 1, -2}, {2, 3, 6}, {3, 4, 2}, {1, 4, 9}};
    int dist[N];
    printf("graph 1 (no negative cycle):\n");
    int bad = bellman_ford(e, 7, 0, dist, 1);
    printf("negative cycle reachable: %s\n", bad ? "yes" : "no");
    struct edge f[8] = {{0, 1, 5}, {0, 2, 4}, {1, 3, 3}, {2, 1, -2}, {2, 3, 6}, {3, 4, 2}, {1, 4, 9}, {4, 1, -8}};
    printf("graph 2 (the edge 4 -> 1 of weight -8 closes the cycle 1, 3, 4 of weight -3):\n");
    bad = bellman_ford(f, 8, 0, dist, 1);
    printf("negative cycle reachable: %s\n", bad ? "yes" : "no");
    return 0;
}

graph 1 (no negative cycle):
pass 1:   0   2   4   8  10
pass 2:   0   2   4   5   7
pass 3:   0   2   4   5   7   (no change: stop)
negative cycle reachable: no
graph 2 (the edge 4 -> 1 of weight -8 closes the cycle 1, 3, 4 of weight -3):
pass 1:   0   2   4   8  10
pass 2:   0  -1   4   5   7
pass 3:   0  -4   4   2   4
pass 4:   0  -7   4  -1   1
negative cycle reachable: yes

After pass $1$ the distances are $0, 2, 4, 8, 10$: the edge $2 \to 1$ of weight $-2$ improved vertex $1$ from $5$ to $2$ after the edge $1 \to 3$ had already used the old value $5$. Pass $2$ repairs this: $3$ becomes $5$ and $4$ becomes $7$. Pass $3$ changes nothing, so the algorithm stops, although up to $V - 1 = 4$ passes are allowed. The result is $0, 2, 4, 5, 7$.

Why $V - 1$ passes are enough

A shortest path from $s$ to $v$ has at most $V - 1$ edges (it is simple). Consider its edges in order, $s = v_0 \to v_1 \to \cdots \to v_k = v$. After pass $1$, $\text{dist}[v_1]$ is correct (the edge $s \to v_1$ was relaxed, and $\text{dist}[s]$ was already correct). After pass $2$, $\text{dist}[v_2]$ is correct, and so on: after pass $i$ the distance of the $i$-th vertex of the path is correct, whatever the order of the edges inside the passes. So $V - 1$ passes make all distances correct. More precisely, after $k$ passes $\text{dist}[v]$ is at most the weight of the best walk from $s$ to $v$ with at most $k$ edges (checked). The order of the edges inside a pass can make convergence faster but not slower: a path graph whose edges are listed in the worst order (last edge first) needs exactly $V - 1$ passes.

Negative cycles

If a negative cycle is reachable, no distance ever settles: every trip around the cycle lowers something. After $V - 1$ passes some edge can still be relaxed. The second graph shows it; the distances of vertices $1$, $3$, $4$ keep dropping.

The cycle $1 \to 3 \to 4 \to 1$ has weight $3 + 2 - 8 = -3$. In pass $4$ (the last allowed) the distance of vertex $1$ is still going down, and the extra check pass finds an edge that can be relaxed: negative cycle reported. The detection is exact: such an edge exists if and only if a negative cycle is reachable from the source (tested against a brute-force enumeration of all simple cycles).

Undirected graphs. An undirected edge is two directed edges, so an undirected edge of negative weight is already a negative cycle (go back and forth). Bellman-Ford cannot give shortest paths in an undirected graph with a negative edge.

Running time and space

Each pass examines all $E$ edges: $\Theta(E)$; there are at most $V - 1$ passes (plus the check): $\Theta(VE)$ in the worst case, space $\Theta(V)$ besides the graph. On a dense graph $E \approx V^2$ this is $\Theta(V^3)$; with an early stop the typical running time is much smaller. A queue-based version that only re-examines the out-edges of vertices whose distance has just improved is faster in practice but has the same worst case.

Shortest paths in a directed acyclic graph

If the graph is a DAG, relax the edges once in the order of a topological sort of the sources of the edges: a vertex is relaxed after all its predecessors are final. Time $\Theta(V + E)$, and negative weights are allowed (there are no cycles). This gives, for example, the longest path in a DAG by negating the weights.

Which algorithm when

Bellman-Ford is a dynamic program: let $D_k(v)$ be the best walk from $s$ to $v$ with at most $k$ edges; then $D_k(v) = \min(D_{k-1}(v), \min_{u \to v} D_{k-1}(u) + w(u, v))$, the pass-by-pass table. It also underlies the distance-vector routing protocol of networks.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Bellman-Ford contrasts with Dijkstra (faster, no negative weights) and with Floyd-Warshall (all pairs); it is a dynamic program over the number of edges (dynamic programming).

PYQs

Let G(V,E) be an undirected, edge-weighted graph
with integer weights. The weight of a path is the
sum of the weights of the edges in that path. The
length of a path is the number of edges in that path.
Let s∈V be a vertex in G. For every u∈V and for
every k ≥0, let dk(u) denote the weight of a shortest
path (in terms of weight) from s to u of length at
most k. If there is no path from s to u of length at
most k, then dk(u)=∞.Consider the statements:
S1: For every k ≥0 and u ∈V, dk+1(u)≤dk(u).
S2: For every (u,v)∈E, if (u,v) is part of a shortest
path (in terms of weight) from s to v, then for every
k≥ 0,dk(u)≤dk(v).
Which one of the following options is correct?

Let G be a weighted directed acyclic graph with m
edges and n vertices. Given G and a source vertex s
in G, which one of the following options gives the
worst case time complexity of the fastest algorithm
to find the lengths of shortest paths from s to all
vertices that are reachable from s in G?

Let G = (V, E) be a directed, weighed graph with
weight function w : E -> R. For some function f : V -
> R, for each edge (u, v) in E, define w'(u, v) as w(u,
v) + f(u) - f(v).
Which one of the options completes the following
sentence so that it is TRUE?
"The shortest paths in G under w are shortest paths
under w' too,
".

What is the time complexity of Bellman-Ford
single-source shortest path algorithm on a complete
graph of n vertices?

Which of the following statement(s) is/are
correct regarding Bellman-Ford
shortest path algorithm?
P. Always finds a negative weighted cycle, if
one exists.
Q. Finds whether any negative weighted cycle
is reachable from the source.

Self-check

Revision card

References