Bellman-Ford Algorithm

Also Known As

TL;DR

Explanation

Bellman-Ford solves the single-source shortest path problem on weighted directed graphs, including graphs with negative edge weights - a case Dijkstra cannot handle. The algorithm initialises the distance to the source as 0 and all other distances as infinity, then relaxes every edge V-1 times, where V is the vertex count. Relaxing an edge (u, v, w) means: if dist[u] + w < dist[v], update dist[v]. After V-1 passes, all shortest paths are guaranteed to be found because any simple path has at most V-1 edges. A V-th pass is used to detect negative cycles: if any edge can still be relaxed, a negative cycle is reachable from the source, and no finite shortest path exists for nodes on or reachable from that cycle. Time complexity is O(V*E), which is slower than Dijkstra's O((V+E) log V), so use Bellman-Ford only when negative weights are possible or when you need cycle detection. Practical applications include currency arbitrage detection (negative log rates), routing protocols like RIP and distance-vector routing, network delay analysis, and constraint systems. Bellman-Ford also serves as a subroutine in Johnson's algorithm for all-pairs shortest paths on sparse graphs with negative weights. In PHP, you might implement it for financial arbitrage checks, dependency graphs with negative weights (rebates, credits), or game economies where certain actions produce net gains.

Diagram

flowchart LR
    A((A<br/>0)) -->|4| B((B))
    A -->|5| C((C))
    B -->|-3| C
    C -->|2| D((D))
    B -->|6| D
    subgraph Passes
        P1[Pass 1: relax all edges] --> P2[Pass 2: refine via B to -3 to C]
        P2 --> P3[Pass V-1: distances settled]
        P3 --> P4{V-th pass<br/>any relaxation?}
        P4 -->|Yes| NC[Negative cycle detected]
        P4 -->|No| OK[Shortest paths valid]
    end
    style OK fill:#238636,color:#fff
    style NC fill:#da3633,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Running only V-1 iterations and skipping the V-th check - you lose negative cycle detection and may return meaningless distances.
• Stopping early without an updated-flag optimisation, or conversely failing to break when no relaxation occurred in a full pass.
• Reporting shortest paths for nodes reachable from a negative cycle - those distances are undefined and should be marked -infinity.
• Using Bellman-Ford on large graphs where all weights are non-negative - Dijkstra with a heap is dramatically faster.
• Confusing edge list representation with adjacency list - Bellman-Ford iterates over edges, so an edge list is often the cleanest structure.

Avoid When

• All edge weights are non-negative - Dijkstra with a heap is much faster.
• The graph is a DAG - a topological-sort relaxation runs in O(V+E).
• Very dense graphs where O(V*E) becomes O(V^3) - consider Floyd-Warshall if you need all-pairs anyway.

When To Use

• Graph contains negative edge weights - Dijkstra will produce wrong answers.
• You must detect negative cycles, e.g. currency arbitrage or exploitable game loops.
• As a subroutine in Johnson's algorithm for all-pairs shortest paths on sparse graphs with negatives.
• Distance-vector routing protocols where nodes propagate distance estimates iteratively.

Code Examples

// WRONG: uses Dijkstra on a graph with negative weights - silently incorrect:
function shortestPath(array $graph, int $src): array {
    $dist = array_fill(0, count($graph), PHP_INT_MAX);
    $dist[$src] = 0;
    $heap = new SplMinHeap();
    $heap->insert([0, $src]);
    while (!$heap->isEmpty()) {
        [$d, $u] = $heap->extract();
        foreach ($graph[$u] as [$v, $w]) {
            // Negative w can produce shorter paths for already-settled nodes,
            // but Dijkstra will not revisit them - result is wrong.
            if ($dist[$u] + $w < $dist[$v]) {
                $dist[$v] = $dist[$u] + $w;
                $heap->insert([$dist[$v], $v]);
            }
        }
    }
    return $dist; // Incorrect when any edge weight is negative
}

/**
 * Bellman-Ford: handles negative weights, detects negative cycles.
 * $edges: list of [u, v, weight]. $v: vertex count.
 * Returns ['dist' => array, 'negativeCycle' => bool].
 */
function bellmanFord(array $edges, int $v, int $src): array {
    $dist = array_fill(0, $v, PHP_INT_MAX);
    $dist[$src] = 0;

    // Relax all edges V-1 times
    for ($i = 0; $i < $v - 1; $i++) {
        $updated = false;
        foreach ($edges as [$u, $to, $w]) {
            if ($dist[$u] !== PHP_INT_MAX && $dist[$u] + $w < $dist[$to]) {
                $dist[$to] = $dist[$u] + $w;
                $updated = true;
            }
        }
        if (!$updated) break; // Early exit optimisation
    }

    // V-th pass: any relaxation implies a reachable negative cycle
    foreach ($edges as [$u, $to, $w]) {
        if ($dist[$u] !== PHP_INT_MAX && $dist[$u] + $w < $dist[$to]) {
            return ['dist' => $dist, 'negativeCycle' => true];
        }
    }

    return ['dist' => $dist, 'negativeCycle' => false];
}

Tags

Related Terms

References

• https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
• https://cp-algorithms.com/graph/bellman_ford.html
• https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/GraphAlgorithms-I.pdf