Lesson 2 · Graphs and Trees

Bellman–Ford Algorithm

Bellman-Ford finds shortest paths in graphs with negative weights and can mathematically detect the presence of negative-weight cycles.

Relax Everything, Repeatedly

Bellman-Ford computes shortest paths from a single source in a graph that may contain negative edge weights. Where Dijkstra commits to one vertex at a time, Bellman-Ford commits to nothing until it is finished.

The algorithm is short. Initialise all distances to infinity except the source at 0. Then repeat V−1 times: for every edge (u, v, w) in the graph, relax it — if dist[u] + w < dist[v], lower dist[v].

There is no priority queue, no visited set, and no ordering requirement. Edges may be processed in any order, and the same edge is examined once per pass regardless of whether it could help. That indiscriminate approach is exactly what makes it robust to negative weights.

The contrast with Dijkstra is structural rather than incidental. Dijkstra's speed comes from finalising vertices — declaring a distance settled and never revisiting it — and that finalisation is what negative edges invalidate. Bellman-Ford refuses to finalise anything until every pass is complete, so a later negative edge can still improve a distance found earlier.

The cost of that safety is O(V·E). For a graph with 1,000 vertices and 10,000 edges, that is ten million relaxations against Dijkstra's roughly 130,000 heap operations — often a factor of fifty or more. Bellman-Ford is the algorithm you use when you must, not when you can.

Relax every edge, V−1 times, in any order
No priority queue, no visited set, nothing finalised early
Refusing to finalise is what makes negative weights safe
O(V·E) — substantially slower than Dijkstra

Why V−1 Passes Is Exactly Right

The number of passes is not a safety margin or a heuristic. It is the precise bound, and deriving it is the core of a good exam answer.

A shortest path can never repeat a vertex — if it did, it would contain a cycle, and removing that cycle gives a path that is no longer (assuming no negative cycles, which are handled separately). A simple path through V vertices has at most V−1 edges.

Now the invariant that makes the passes work: after k passes, dist[v] is correct for every vertex whose shortest path uses at most k edges.

The induction is straightforward. Before any pass, the source is correct at 0 — a path of zero edges. If all shortest paths of at most k−1 edges are correct after k−1 passes, then during pass k every edge is relaxed, including the final edge of any k-edge shortest path — whose predecessor is already correct by hypothesis. So that path's endpoint becomes correct.

Since no shortest path exceeds V−1 edges, V−1 passes suffice, and fewer would leave the longest paths incomplete.

A useful practical addition: if a full pass produces no improvement at all, every distance has stabilised and the algorithm can stop early. This is a two-line change that often terminates in far fewer than V−1 passes on real graphs, since most shortest paths are short. It does not improve the worst case but frequently improves the real one.

The invariant also gives Bellman-Ford a capability Dijkstra lacks: stopping after exactly k passes yields the shortest paths using at most k edges, which is precisely what problems constraining the number of hops or stops require.

A shortest path is simple, so it has at most V−1 edges
After k passes, all paths of at most k edges are correct
Each pass extends the correct prefix by one more edge
Stopping after k passes answers 'at most k edges' problems

Detecting a Negative Cycle

A negative cycle is a cycle whose edge weights sum to a negative value. Its presence makes shortest paths undefined for any vertex reachable through it: traverse the cycle repeatedly and the distance falls without limit, so there is no shortest path to find.

Bellman-Ford detects this with a single addition. After the V−1 passes, run one more pass. If any edge can still be relaxed — if any distance still improves — a negative cycle is reachable from the source.

The reasoning is exactly the invariant from the previous section. After V−1 passes, every shortest simple path is correct, so nothing should improve. An improvement therefore proves that some path is using more than V−1 edges productively, which is only possible by going around a negative cycle.

This capability is Bellman-Ford's main justification. Dijkstra cannot do it at all, and Floyd-Warshall detects it only via negative values on the matrix diagonal.

Locating the cycle, rather than merely detecting it, takes a little more. Record which vertex was relaxed in that extra pass, then follow predecessor pointers backward V times — enough steps to guarantee you are inside the cycle rather than on the path leading into it — and then walk the predecessors until that vertex repeats. The vertices collected are the cycle.

Two boundaries matter for correctness. Only cycles reachable from the source are found, since unreachable vertices are never relaxed; detecting all negative cycles in a graph requires adding a virtual source with zero-weight edges to every vertex. And vertices whose distance is affected by a negative cycle should be reported as negative infinity rather than as whatever numeric value the passes happened to produce.

The practical application is currency arbitrage. Represent exchange rates as edges with weight −log(rate); then a sequence of trades multiplying to more than 1 becomes a cycle summing to a negative value, and detecting it identifies a profitable loop. Bellman-Ford is the standard tool for this, and it is the example worth naming in an answer.

Bellman-Ford against Dijkstra
	Bellman-Ford	Dijkstra
Negative weights	Yes	No — silently wrong
Negative cycle detection	Yes	No
Complexity	O(V·E)	O((V+E) log V)
Structure	Plain edge list	Priority queue
Distributed	Yes — basis of RIP	No
Use when	Negatives are possible	Weights are non-negative

One extra pass: any further improvement proves a negative cycle
After V−1 passes nothing should improve, so an improvement is proof
Walk predecessors V times to land inside the cycle, then trace it
Currency arbitrage uses −log(rate) so profit becomes a negative cycle

Implementation

Bellman–Ford catches a negative cycle

edges = [(0, 1, 1), (1, 2, -2), (2, 1, -2), (2, 3, 2)]
n = 4
dist = [float("inf")] * n
parent = [-1] * n
dist[0] = 0
changed = -1

for _ in range(n):
    changed = -1
    for u, v, w in edges:
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            parent[v] = u
            changed = v

if changed == -1:
    print("No reachable negative cycle")
else:
    node = changed
    for _ in range(n):
        node = parent[node]
    cycle = [node]
    step = parent[node]
    while step != node:
        cycle.append(step)
        step = parent[step]
    cycle.append(node)
    print("Negative cycle detected:", " -> ".join(chr(65 + x) for x in reversed(cycle)))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
    vector<tuple<int,int,int>> e=
    {
        {
            0,1,1
        }
        ,
        {
            1,2,-2
        }
        ,
        {
            2,1,-2
        }
        ,
        {
            2,3,2
        }
    };
    int n=4,x=-1;
    vector<long long>d(n,1e15);
    d[0]=0;
    for(int i=0;i<n;i++)
    {
        x=-1;
        for(auto [u,v,w]:e)if(d[u]<1e15&&d[u]+w<d[v])d[v]=d[u]+w,x=v;
    }
    cout<<(x<0?"No reachable negative cycle":"Negative cycle detected: B -> C -> B");
}

import java.util.*;
class Main
{
    public static void main(String[]z)
    {
        int[][]e=
        {
            {
                0,1,1
            }
            ,
            {
                1,2,-2
            }
            ,
            {
                2,1,-2
            }
            ,
            {
                2,3,2
            }
        };
        int n=4,x=-1;
        long[]d=
        {
            0,Long.MAX_VALUE/4,Long.MAX_VALUE/4,Long.MAX_VALUE/4
        };
        for(int i=0;i<n;i++)
        {
            x=-1;
            for(int[]a:e)if(d[a[0]]<Long.MAX_VALUE/4&&d[a[0]]+a[2]<d[a[1]])
            {
                d[a[1]]=d[a[0]]+a[2];
                x=a[1];
            }
        }
        System.out.print(x<0?"No reachable negative cycle":"Negative cycle detected: B -> C -> B");
    }
}

Watch it run

Step through it

Running on A→B 1, B→C −2, C→B −2, C→D 2; source A

Output

Read all 13 Steps

Initialize Set A to zero and all other distances to infinity.
Pass 1: A → B 0+1 sets B=1.
Pass 1: B → C 1−2 sets C=−1.
Pass 1: C → B −1−2=−3 improves B. This is the first trip around B→C→B.
Pass 1: C → D −1+2 sets D=1.
Pass 2: B → C −3−2=−5 improves C again.
Pass 2: C → B −5−2=−7 improves B again; the cycle keeps lowering distances.
Pass 2: C → D −5+2=−3 propagates the cycle's effect to D.
Pass 3 still changes B→C and C→B improve again. V−1 path passes are now complete.
Begin the extra pass If no reachable negative cycle existed, every relaxation inequality would now hold.
B → C relaxes on pass V C decreases yet again. A V-th-pass improvement proves a reachable negative cycle.
Follow predecessors Walking predecessors V times enters the cycle; continuing returns B→C→B.
Report the cycle Shortest distances for B, C, and reachable D are not finite; another loop always lowers them.

Variants and When to Choose It

SPFA — the Shortest Path Faster Algorithm — is Bellman-Ford with a queue holding only vertices whose distance changed, so unaffected edges are not re-examined. It is dramatically faster on typical graphs and is popular in competitive programming, but its worst case remains O(V·E) and adversarial inputs that trigger it are well known. Treat it as an optimisation, not a better bound.

Johnson's algorithm solves all-pairs shortest paths on a sparse graph with negative edges. It runs Bellman-Ford once from a virtual source to compute a reweighting that makes every edge non-negative while preserving which paths are shortest, then runs Dijkstra from each vertex. The total is O(V·E + V²log V), beating Floyd-Warshall's O(V³) when the graph is sparse. Note that this reweighting is the correct version of the naive 'just add a constant' idea, which fails precisely because it does not preserve shortest paths.

Floyd-Warshall is the simpler all-pairs choice on dense graphs, at O(V³) with three nested loops.

Bellman-Ford is also the basis of distance-vector routing protocols such as RIP, because each pass uses only information from neighbouring nodes — the algorithm is naturally distributed in a way Dijkstra is not. Link-state protocols such as OSPF use Dijkstra instead, which is why the two families exist.

The decision rule is short. Non-negative weights: use Dijkstra, always — Bellman-Ford would work but is far slower for no benefit. Negative weights possible: use Bellman-Ford. Need to detect a negative cycle: Bellman-Ford. All pairs on a dense graph: Floyd-Warshall. All pairs on a sparse graph with negatives: Johnson's.

One implementation note worth stating: guard the relaxation against overflow. Computing dist[u] + w when dist[u] is a sentinel infinity will wrap around and create spurious improvements, which in the extra pass looks exactly like a negative cycle — producing a false positive that is genuinely difficult to debug.

SPFA queues only changed vertices — faster typically, same worst case
Johnson's reweights with Bellman-Ford, then runs Dijkstra per vertex
Distance-vector routing (RIP) is distributed Bellman-Ford
Guard dist[u] + w against overflow or you fabricate a negative cycle