Bellman-Ford algorithm

The Bellman-Ford algorithm computes shortest paths from a single source vertex to every other vertex in a weighted Graph, allowing negative edge weights. It also detects negative-weight cycles — situations where shortest paths don’t exist because you can keep going around the loop and shrink the total weight forever.

It’s the natural counterpart to Dijkstra: slower ($O(VE)$ vs. $O((V+E)\log V)$), but it works on graphs Dijkstra can’t handle.

The idea

Dijkstra grows a cloud of finalised vertices and never revisits one. That works only when distances increase monotonically as you grow the cloud — true for non-negative weights, but breaks down with negatives.

Bellman-Ford takes a different approach: keep relaxing every edge, over and over. After $k$ rounds of relaxing all $E$ edges, the distance estimate $d(v)$ is correct for every vertex reachable from the source by a path of at most $k$ edges. Since any shortest path uses at most $V-1$ edges (more than that means a cycle, which can’t help if there are no negative cycles), $V-1$ rounds are enough.

Algorithm

1. Initialise $d(\text{source})=0$ and $d(v)=\infty$ for every other vertex.
2. Repeat $V-1$ times: for every edge $(u,v)$ with weight $w$, relax: $d(v)\leftarrow \min \{d(v),d(u)+w\}$
3. After the $V-1$ rounds, do one more pass over every edge. If any relaxation still improves a distance, the graph contains a negative-weight cycle reachable from the source — report it. Otherwise the distances are final.

The relaxation step is identical to Dijkstra’s. The difference is that Bellman-Ford relaxes every edge in every round, instead of carefully picking which vertex to expand.

Why $V-1$ rounds

Claim: after round $k$, $d(v)$ is the weight of the shortest path from the source to $v$ that uses at most $k$ edges.

Proof by induction. Base case $k=0$: only the source has finite distance, which is correct. Inductive step: at the start of round $k$, every vertex has the right distance for paths of length at most $k-1$. The relaxations in round $k$ extend each of those paths by one more edge — so by the end of round $k$, every vertex has the right distance for paths of length at most $k$.

A simple shortest path has at most $V-1$ edges (it can’t visit the same vertex twice without forming a cycle). So $V-1$ rounds suffice.

Detecting negative cycles

After $V-1$ rounds, the distances are final — unless there’s a negative cycle reachable from the source. A negative cycle means you can always find a shorter path by going around it once more. So one more relaxation pass: if anything improves, a reachable negative cycle exists.

The cycle can also be reconstructed using predecessor pointers: start from a vertex whose distance just improved, walk backward through pred for $V$ steps (guaranteed to land inside the cycle), then walk one more loop to extract it.

Implementation

#define V 5      // number of vertices
#define E 8      // number of edges
 
typedef struct { int src, dst, weight; } Edge;
 
bool BellmanFord(Edge edges[E], int source, int dist[V]) {
    for (int i = 0; i < V; i++) dist[i] = INT_MAX;
    dist[source] = 0;
    
    // V-1 relaxation rounds
    for (int i = 0; i < V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j].src, v = edges[j].dst, w = edges[j].weight;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    
    // One more pass to detect a negative cycle
    for (int j = 0; j < E; j++) {
        int u = edges[j].src, v = edges[j].dst, w = edges[j].weight;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            return false;       // negative cycle reachable
        }
    }
    return true;
}

The structure is intentionally dumb: just relax every edge over and over. No priority queue, no sorting, no bookkeeping beyond the distance array.

Big O

• Time: $O(V\cdot E)$ — $V-1$ rounds, $E$ relaxations each.
• Space: $O(V)$ for the distance array (and the predecessor array if you want to reconstruct paths).

For a sparse graph ($E=O(V)$) this is $O(V^2)$ — same as the naïve array-based Dijkstra. For a dense graph ($E=O(V^2)$) it’s $O(V^3)$, much slower than Dijkstra’s $O(V^2)$ on the same graph (the simple array-PQ Dijkstra, which beats the heap version $O((V+E)\log V)=O(V^2\log V)$ when the graph is dense). On dense graphs the heap version of Dijkstra is not the right comparison; the array-PQ version is. The cost of generality.

When to use which

Use Dijkstra when all edge weights are non-negative. It’s faster.

Use Bellman-Ford when:

• Some edge weights are negative.
• You need to detect negative cycles (e.g., currency arbitrage detection — a negative cycle in $\log (\text{exchange rate})$ space means a profitable round trip).
• You’re implementing a distance-vector routing protocol (RIP uses a distributed Bellman-Ford).

For all-pairs shortest paths with negative weights, see the Floyd-Warshall algorithm — same family of dynamic-programming relaxation, but $O(V^3)$ for the full all-pairs answer.