Bellman-Ford Algorithm

Lecture slides (PDF)

Dijkstra’s algorithm fails when the graph contains negative-weight edges: once a vertex is finalised, a later negative-cost shortcut could still improve its distance, but Dijkstra never revisits finalised vertices.

In general, we might run into a negative cycle — a cycle where continuously looping through it reduces the total path length without bound. To avoid this, we define a path as a walk without repeated vertices (also known as a simple path).

The Bellman-Ford algorithm relaxes all edges in each of $n-1$ rounds. Any shortest path in a graph with $n$ vertices is a simple path, so it uses at most $n-1$ edges.

Algorithm
function bellman_ford(graph, source)
    for each vertex v
        dist[v] = ∞
        parent[v] = 0
    end
    dist[source] = 0

    for i = 1 to n-1
        for each edge (u, v) with weight w
            if dist[u] + w < dist[v]      # edge (u,v) is tense
                dist[v]   = dist[u] + w
                parent[v] = u
            end
        end
    end

    # Negative-cycle check
    for each edge (u, v) with weight w
        if dist[u] + w < dist[v]
            report "negative cycle reachable from source"
        end
    end

    return dist, parent
end

Example. We run Bellman-Ford from source vertex 1 on the graph below. The negative edge $2 \to 3$ (weight $-4$) makes the path $1 \to 2 \to 3 \to 4$ cheaper than the direct edge $1 \to 4$, but it takes two rounds for this improvement to propagate all the way to vertex 4.

Round 0: Initialise. dist[1] $= 0$, dist[v] $= \infty$ for all other $v$.

Round 1. Relax $1 \to 2$: dist[2] $= 2$. Relax $1 \to 4$: dist[4] $= 8$. Edges $2 \to 3$ and $3 \to 4$ have no effect since dist[2] $= \infty$ and dist[3] $= \infty$ at the start of this round.

Round 2. Relax $2 \to 3$: dist[3] $= 2 + (-4) = -2$. No other edge improves.

Round 3. Relax $3 \to 4$: dist[4] $= -2 + 1 = -1$, improving from 8. No other edge improves. Distances are now final.

The direct edge $1 \to 4$ (weight 8) is beaten by the path $1 \to 2 \to 3 \to 4$ (weight $2 - 4 + 1 = -1$). Bellman-Ford discovers this in two waves: round 1 propagates to vertex 2, round 2 propagates to vertex 3 via the negative edge, and round 3 propagates to vertex 4.

Negative Cycle Detection

After $n-1$ rounds, perform one additional scan of all edges. If any edge $(u, v)$ is still tense, i.e., dist$[u] + w(u, v) <$ dist$[v]$ — then there is a negative-weight cycle reachable from the source. Along such a cycle, distances can be decreased indefinitely, so no finite shortest path exists.

Correctness

Claim. After round $k$, dist$[v]$ is at most the weight of the shortest path from $s$ to $v$ using at most $k$ edges.

Proof by induction on $k$. After round $0$, dist$[s] = 0$ and dist$[v] = \infty$ for $v \ne s$, matching the shortest paths using $0$ edges. Assume the claim holds after round $k-1$. In round $k$, consider any vertex $v$ and its shortest path $P$ using at most $k$ edges. Let $(u, v)$ be the last edge of $P$; then $P$ without its last edge is a path from $s$ to $u$ using at most $k-1$ edges. By the inductive hypothesis, dist$[u]$ after round $k-1$ is at most the weight of that sub-path. When we relax $(u, v)$ in round $k$:

\[\text{dist}[v] \;\leq\; \text{dist}[u] + w(u,v) \;\leq\; \text{weight of } P.\]

This holds for every shortest path using $\le k$ edges, completing the induction.

Since any simple shortest path has at most $n-1$ edges (more would imply a cycle, which is non-negative by assumption), running $n-1$ rounds gives the exact shortest-path distances. $\square$

Running Time

Each round scans all $m$ edges once. With $n - 1$ rounds, the total time is $O(nm)$.

This is slower than Dijkstra ($O((n+m)\log n)$), but Bellman-Ford handles negative edges and detects negative cycles, making it indispensable when those cases arise.

Julia Implementation
function bellman_ford(n, adj, source)
    # adj[u] is a list of (v, weight) pairs
    dist   = fill(Inf, n)
    parent = zeros(Int, n)
    dist[source] = 0.0

    for _ in 1:n-1
        updated = false
        for u in 1:n
            dist[u] == Inf && continue
            for (v, w) in adj[u]
                if dist[u] + w < dist[v]
                    dist[v]   = dist[u] + w
                    parent[v] = u
                    updated   = true
                end
            end
        end
        updated || break   # early exit if no update occurred
    end

    # Negative-cycle check
    for u in 1:n
        for (v, w) in adj[u]
            if dist[u] + w < dist[v]
                error("negative cycle reachable from source")
            end
        end
    end

    return dist, parent
end