Chapter 74

Home

Bellman-Ford Algorithm

Bellman-Ford finds shortest paths with negative edge weights — something Dijkstra can't handle. It also detects negative cycles (where the shortest path doesn't exist). Trade-off: O(V×E) instead of O((V+E) log V).

The Algorithm

Relax all edges V−1 times. After iteration k, distances to nodes reachable in ≤ k edges are correct. Then check for negative cycles: if any distance still improves on the V-th pass, a negative cycle exists.

C++ — Bellman-Ford

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

vector bellman_ford(vector& edges, int V, int start) {
    vector dist(V, LLONG_MAX / 2);
    dist[start] = 0;

    // Relax all edges V-1 times
    for (int i = 0; i < V - 1; i++)
        for (auto& e : edges)
            if (dist[e.u] + e.w < dist[e.v])
                dist[e.v] = dist[e.u] + e.w;

    // Check for negative cycles
    for (auto& e : edges)
        if (dist[e.u] + e.w < dist[e.v])
            return {};  // negative cycle detected

    return dist;
}

// O(V × E) — for V=1000, E=10⁴:  ~10M operations

Rust — Bellman-Ford

struct Edge { u: usize, v: usize, w: i64 }

fn bellman_ford(edges: &[Edge], v: usize, start: usize) -> Option> {
    let mut dist = vec![i64::MAX / 2; v];
    dist[start] = 0;

    for _ in 0..v - 1 {
        for e in edges {
            if dist[e.u] + e.w < dist[e.v] {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }
    for e in edges {
        if dist[e.u] + e.w < dist[e.v] { return None; }
    }
    Some(dist)
}

Key Takeaways