Bellman–Ford Algorithm

Why do we need another shortest-path algorithm?

Dijkstra’s algorithm is fast, but it trusts that a node’s distance never gets better once it is picked. That is true when every edge weight is zero or positive. With a negative edge it can fail.

Look at the graph in the 3D model. From S, the direct edge to A costs 4, and the edge to B costs 5. Dijkstra picks A first (4 < 5) and declares dist[A] = 4 final. But B → A has weight −3, so the route S → B → A costs 5 − 3 = 2. Dijkstra never goes back to fix A.

Negative weights are not just a puzzle. They model refunds, energy gained, exchange-rate gains or any cost that can go down.

The idea: relax every edge, again and again

Relaxing an edge u → v with weight w means checking whether going through u is a shortcut:

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Bellman–Ford does not choose nodes cleverly. It simply relaxes every edge, in a fixed order, and repeats that whole pass V − 1 times. Why V − 1? A shortest path never visits a node twice, so it uses at most V − 1 edges. Each pass makes at least one more edge of every shortest path correct, so after V − 1 passes all of them are correct.

If a pass changes nothing, nothing will ever change again, so you can stop early.

Pass by pass

With the edges listed in the “unlucky” order (D→E, C→E, C→D, A→D, B→C, A→C, B→A, S→B, S→A), improvements creep forward slowly:

List the edges outwards from S instead, and the first pass already finds every final distance. The second pass changes nothing and the algorithm stops. The order of edges changes the speed, never the answer.

Detecting negative cycles

If the graph contains a loop whose weights add up to less than zero, a negative cycle, you can go round it forever and make the path as cheap as you like. Then shortest paths simply don’t exist.

Bellman–Ford spots this with one extra pass: after V − 1 passes every distance should be final. If any edge can still be relaxed, a negative cycle is reachable from the source. Following the prev pointers back from that edge leads into the cycle itself, which is how the 3D model can highlight it.

Code

def bellman_ford(nodes, edges, source):
    dist = {v: float("inf") for v in nodes}
    prev = {v: None for v in nodes}
    dist[source] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                changed = True
        if not changed:
            break                       # nothing can improve any more
    for u, v, w in edges:               # one extra pass
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle reachable from the source")
    return dist, prev

edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 4), ("B", "C", 6),
         ("A", "D", 7), ("C", "D", 2), ("C", "E", 3), ("D", "E", -2)]
dist, prev = bellman_ford("SABCDE", edges, "S")
print(dist)   # {'S': 0, 'A': 2, 'B': 5, 'C': 6, 'D': 8, 'E': 6}

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

struct Edge { int u, v, w; };

// Fills dist; returns false if a negative cycle is reachable from src.
bool bellmanFord(int n, const vector<Edge>& edges, int src, vector<long long>& dist) {
    const long long INF = LLONG_MAX / 4;
    dist.assign(n, INF);
    dist[src] = 0;
    for (int pass = 1; pass < n; pass++) {
        bool changed = false;
        for (auto [u, v, w] : edges)
            if (dist[u] != INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
        if (!changed) break;
    }
    for (auto [u, v, w] : edges)
        if (dist[u] != INF && dist[u] + w < dist[v]) return false;   // negative cycle
    return true;
}

int main() {
    // 0 S, 1 A, 2 B, 3 C, 4 D, 5 E
    vector<Edge> edges = {{0,1,4},{0,2,5},{2,1,-3},{1,3,4},{2,3,6},{1,4,7},{3,4,2},{3,5,3},{4,5,-2}};
    vector<long long> dist;
    if (bellmanFord(6, edges, 0, dist))
        for (long long d : dist) cout << d << " ";   // 0 2 5 6 8 6
}

Bellman–Ford vs Dijkstra

Use Dijkstra when all weights are non-negative, because it is much faster. Use Bellman–Ford when weights can be negative or when you must detect negative cycles.

Where is it used?

• Distance-vector routing (RIP): every router repeatedly improves its distance table using its neighbours’ tables. It is Bellman–Ford spread across a network.
• Currency arbitrage: take weights −log(rate). A negative cycle is a loop of exchanges that ends with more money than you started with.
• Johnson’s algorithm uses one Bellman–Ford run to re-weight a graph so Dijkstra can then be used from every node.
• Scheduling with constraints like “task B starts at most 3 hours after task A” turns into shortest paths with negative edges.

Common mistakes

• Running V passes and treating the last one as normal. The V-th pass is the cycle check.
• Using Bellman–Ford on an undirected graph with a negative edge. That edge alone, walked back and forth, is already a negative cycle.
• Adding to “infinity” in code: INF + w can overflow. Skip edges whose start is still unreachable.
• Thinking a bad edge order gives a wrong answer. It only needs more passes.