Bellman-Ford

Shortest paths with negative edges, plus negative-cycle detection. · 9 min read

Concept

Bellman-Ford solves single-source shortest paths even when some edges have negative weights. It is slower than Dijkstra, but it works in a more general setting and can detect negative cycles reachable from the start.

Interactive visualization: Bellman-Ford simulation: repeated relaxation — step through it frame by frame on this page.

Relaxation

Relaxation is the one operation all shortest-path algorithms share: if going through u improves the best known distance to v, update it.

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
}

Why V-1 passes are enough

Bellman-Ford dynamic-programming view

a shortest simple path uses at most V−1 edges — If it repeats a vertex, it contains a cycle.
pass 1 finds best paths using ≤1 edge — Every edge is relaxed once.
pass k finds best paths using ≤k edges — Induction: extend a best ≤k−1 edge path by one edge.
after V−1 passes — All simple shortest paths have had enough edges to appear.

Result: O(VE)

Negative cycle detection

After V−1 passes, do one more pass. If any edge can still relax, the graph has a reachable negative cycle. Distances are not well-defined because looping around that cycle keeps making the path cheaper forever.

C++ sketch

struct Edge { int u, v; long long w; };
vector<long long> dist(n, INF);
dist[start] = 0;

for (int pass = 1; pass <= n - 1; pass++) {
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
        }
    }
}

bool negativeCycle = false;
for (auto [u, v, w] : edges) {
    if (dist[u] != INF && dist[u] + w < dist[v]) {
        negativeCycle = true;
    }
}