Bellman-Ford

Graphs O(V · E) O(V)

Shortest paths from a source that also works with negative edge weights, by relaxing every edge V−1 times.

Source

1/28

Initialise every distance to ∞.

InvariantAfter k passes, every shortest path using at most k edges has been found. V−1 passes cover every simple path.

currentfrontiervisitedtree edge

bellman-ford.c

#define V 6
#define INF 1000000
 
int bellmanFord(int graph[V][V], int src, int dist[V]) {
    for (int i = 0; i < V; i++) dist[i] = INF;
    dist[src] = 0;
 
    for (int pass = 1; pass < V; pass++) {
        for (int u = 0; u < V; u++) {
            if (dist[u] == INF) continue;
            for (int v = 0; v < V; v++) {
                if (graph[u][v] &&
                    dist[u] + graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
            }
        }
    }
 
    /* One extra sweep: an edge that still relaxes after V-1
       passes proves a negative cycle is reachable. */
    for (int u = 0; u < V; u++)
        for (int v = 0; v < V; v++)
            if (graph[u][v] && dist[u] != INF &&
                dist[u] + graph[u][v] < dist[v])
                return 0;
    return 1;
}

How Bellman-Ford works

Relax every edge, V−1 times. After pass k every shortest path using ≤ k edges is correct; a V-th improving pass would prove a negative cycle.

Best case

Converges early if a pass changes nothing.

Worst case

O(V·E) — every pass touches every edge.

When to use it

Graphs with negative edge weights, or when you must detect negative cycles.