Bellman-Ford algorithm

Bellman-Ford computes single-source shortest paths even when some edge weights are negative. It repeatedly relaxes every edge for V − 1 rounds (maximum edges in a simple path), then performs one extra pass to detect a negative cycle reachable from the source. If such a cycle exists, shortest paths are undefined because total path cost can decrease forever.

1) When to use

• Use Dijkstra when all weights are nonnegative (usually faster).
• Use Bellman-Ford when negative edges may appear and you need cycle detection.
• Works on directed graphs directly; for undirected graphs, any negative undirected edge implies a 2-edge negative cycle.

2) Core idea

Let dist[v] be the best known cost from source s to v. Initialize dist[s]=0, others to INF. For each round, scan every edge u→v with weight w: if dist[u] + w < dist[v], update dist[v]. After V−1 rounds, shortest simple paths are settled. Any further improvement indicates a reachable negative cycle.

3) Example graph (has negative edges, no negative cycle)

Edges (u -> v : w):
0->1: 6,  0->2: 7,  1->2: 8,  1->3: 5,  1->4: -4,
2->3: -3, 2->4: 9,  3->1: -2, 4->0: 2,  4->3: 7

Source s = 0, expected final dist: [0, 2, 7, 4, -2]

4) C — Bellman-Ford (edge list)

#include <limits.h>
#include <stdio.h>

#define V 5
#define E 10
#define INF (LLONG_MAX / 4)   /* large safe sentinel */

typedef long long ll;

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

static Edge edges[E] = {
    {0,1, 6}, {0,2, 7}, {1,2, 8}, {1,3, 5}, {1,4,-4},
    {2,3,-3}, {2,4, 9}, {3,1,-2}, {4,0, 2}, {4,3, 7}
};

int bellman_ford(int s, ll dist[V]) {
    for (int i = 0; i < V; i++) dist[i] = INF;
    dist[s] = 0;

    /* Relax all edges V-1 times */
    for (int round = 1; round <= V - 1; round++) {
        int changed = 0;
        for (int i = 0; i < E; i++) {
            int u = edges[i].u, v = edges[i].v;
            ll w = edges[i].w;
            if (dist[u] == INF) continue;            /* source not reaching u yet */
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = 1;
            }
        }
        if (!changed) break;   /* early stop if round made no update */
    }

    /* One more pass: any improvement => reachable negative cycle */
    for (int i = 0; i < E; i++) {
        int u = edges[i].u, v = edges[i].v;
        ll w = edges[i].w;
        if (dist[u] != INF && dist[u] + w < dist[v])
            return 0;   /* negative cycle exists */
    }
    return 1;       /* valid shortest paths */
}

int main(void) {
    ll dist[V];
    if (!bellman_ford(0, dist)) {
        printf("reachable negative cycle\n");
        return 1;
    }
    for (int i = 0; i < V; i++)
        printf("dist[%d] = %lld\n", i, dist[i]);
    return 0;
}

5) Complexity

• Time: O(VE) in worst case (V−1 full relaxation passes plus one cycle-check pass).
• Space: O(V + E) for distance array and edge list.
• Slower than Dijkstra on nonnegative graphs, but strictly more general because of negative-edge support.

6) Trace (source = 0)

Final shortest costs from 0: [0, 2, 7, 4, -2]. Extra cycle-check pass makes no update, so there is no reachable negative cycle.