Bellman–Ford: negative weights and cycles

Why another pass can help

Edges are directed: each arrow permits travel only in its direction. A weight may represent an additive cost with a credit or discount, so it can be negative. This is not a maze where you can automatically walk back along every passage. In an undirected graph, a usable negative edge traversed back and forth already creates a negative closed walk.

Dijkstra permanently settles a smallest tentative distance using nonnegative weights. A negative edge breaks that guarantee. Bellman–Ford does not settle vertices that way: it scans the entire edge list repeatedly and keeps improving distance estimates. Unlike Dijkstra with one goal, it cannot stop just because the goal was reached or improved.

One edge, one possible improvement

Initially d(start)=0 and other distances are infinity. For u → v with weight w, try d(u)+w. If the source u is reachable and this is strictly below d(v), update both d(v) and its parent edge. This operation is relaxation. Equal costs leave the parent unchanged; unreachable sources are skipped without adding to infinity.

The example scans edges in input order and updates distances in place. A change can therefore be used by a later edge in the same pass. A pass is not a simultaneous wave, and its number is not an exact limit on how many edges the displayed routes contain. Different edge orders may change intermediate states, pass counts and equal-cost routes.

From cost four to cost three

The initial order is A → G (2), B → A (−4), S → A (2), S → B (5). The first pass skips the first two edges because their sources are still unreachable, then sets d(A)=2 and d(B)=5. G still has infinity.

Pass two first sets d(G)=4 through A. Later, B → A improves d(A) from 2 to 5−4=1. A → G has already been scanned, so that new value reaches G on pass three: d(G)=1+2=3. The final route is S → B → A → G, costing 5−4+2=3. This route uses more edges than S → A → G, which costs four.

Why at most V−1 main passes

Without a reachable negative cycle, a shortest route can be chosen without repeated vertices, so it has at most V−1 edges. After pass k, every vertex whose shortest route needs at most k edges has its final distance. In-place updates may propagate farther in one pass. Thus V−1 main passes suffice for finite reachable shortest distances.

If a complete pass changes nothing, every reachable edge already satisfies d(v) ≤ d(u)+w. Another identical scan cannot improve anything, so this implementation stops early. It does not stop halfway through a pass. With V=1 there are no main passes, but the cycle check still runs, so a negative self-loop is detected.

A negative cycle and its downstream vertices

After V−1 changing passes, test all edges once more using the unchanged distance estimates. A strict improvement from a reachable source proves that a negative cycle is reachable from the start. An isolated negative cycle does not trigger this test: its sources still have infinity.

The player also classifies the consequence for each vertex. Seed the heads of still-improvable edges, then mark every vertex reachable from them. Those distances are −∞: traversing a negative cycle more times can lower the cost without bound before continuing to the vertex. The red area means affected vertices; it is not an extracted cycle witness.

A goal may be unreachable (∞), have a finite minimum, or be reachable with no finite minimum (−∞). A negative cycle matters to the goal only if it is reachable from the start and can reach the goal. Try the side-cycle example: the cycle is reachable, yet G keeps cost four. A negative cycle in a disconnected component leaves the initial finite route unchanged. No route is reconstructed for an unreachable or unbounded goal.

Reading and changing the example

Amber marks the edge being scanned; the sentence above the graph shows the old source distance, candidate and previous destination estimate. A complete main pass increments the pass counter. The cycle check is labeled separately. Green shows the saved route. Red vertices are reachable from a detected negative cycle.

Scanned edges counts every edge inspected in the main passes and the control scan, including edges with unreachable sources. Distance updates counts strict improvements in the main passes, including infinity-to-finite changes. Forward marking and path reconstruction are separate stages and do not increment those two counters. During unfinished passes, finite distances are estimates rather than promised minimum costs.

Choose a preset, start and goal, or edit an edge weight. Invalid input preserves the current valid run. The demo accepts 1–8 uniquely labeled vertices, up to 32 directed edges without duplicate ordered pairs, and integer weights from −99 to 99; self-loops and zero weights are allowed. You can pause, step in either direction, seek, share a paused snapshot, expand the player or save a silent video of the entire run.

Algorithm memory and playback history

Main passes and the extra check take O(VE+V) time including initialization, usually written O(VE) for graphs with edges. The forward-marking extension scans the edge list for each queued vertex, adding O(VE). Working arrays, the seed set and the queue use O(V) memory, excluding the input graph. An adjacency index could make marking O(V+E), with extra storage.

The visualization freezes one graph copy in O(V+E) space and saves O(V) data per event. There are O(VE+V) events, so playback history has an O(V²(E+1)) bound in addition to the graph. That stored history is a UI cost, not Bellman–Ford’s working-memory bound. Animation speed is not a CPU benchmark.

JavaScript implementation

The compact function below computes the result without visualization history. Edges are ordered {from,to,weight} objects; vertices are numbered 0 through n−1. It uses the same in-place order, strict comparisons, early stop and affected-vertex classification as the demo. Weights and intermediate costs must be safe JavaScript integers; overflow is rejected. The demo’s smaller limits keep its saved history and labels manageable.

function bellmanFord(n, edges, start, target) {
    const valid = v => Number.isInteger(v) && v >= 0 && v < n;
    if (!Number.isInteger(n) || n < 1 || !valid(start) || !valid(target))
        throw Error("Invalid vertices");
    for (const e of edges)
        if (!valid(e.from) || !valid(e.to) || !Number.isSafeInteger(e.weight))
            throw Error("Expected integer edge weights");
    const d = Array(n).fill(Infinity), parent = Array(n).fill(null);
    const affected = Array(n).fill(false);
    d[start] = 0;
    let fixed = false;
    for (let pass = 1; pass < n; pass++) {
        let changed = false;
        for (let id = 0; id < edges.length; id++) {
            const {from, to, weight} = edges[id];
            if (d[from] === Infinity) continue;
            const candidate = d[from] + weight;
            if (!Number.isSafeInteger(candidate)) throw Error("Cost overflow");
            if (candidate < d[to]) {
                d[to] = candidate; parent[to] = id; changed = true;
            }
        }
        if (!changed) { fixed = true; break; }
    }
    const queue = [];
    if (!fixed) for (const {from, to, weight} of edges) {
        if (d[from] === Infinity) continue;
        const candidate = d[from] + weight;
        if (!Number.isSafeInteger(candidate)) throw Error("Cost overflow");
        if (candidate < d[to] && !affected[to]) {
            affected[to] = true; queue.push(to);
        }
    }
    const negativeCycle = queue.length > 0;
    for (let head = 0; head < queue.length; head++)
        for (const {from, to} of edges)
            if (from === queue[head] && !affected[to]) {
                affected[to] = true; queue.push(to);
            }
    for (let v = 0; v < n; v++) if (affected[v]) {
        d[v] = -Infinity; parent[v] = null;
    }
    const result = affected[target] ? "unbounded"
        : d[target] === Infinity ? "unreachable" : "finite";
    const path = [];
    if (result === "finite") {
        let v = target;
        for (let count = 0; ; count++) {
            if (count >= n) throw Error("Invalid parent chain");
            path.push(v);
            if (v === start) break;
            v = edges[parent[v]].from;
        }
        path.reverse();
    }
    return {distance: d, parentEdge: parent, affected, negativeCycle, result, path};
}