Bellman-Ford Algorithm: Working, Explanation, and Shortest Path with Negative Weights

I first turned to the Bellman-Ford algorithm when I ran into a graph with negative edge weights and realized that Dijkstra’s algorithm, my usual go-to for shortest paths, simply couldn’t be trusted there. Bellman-Ford is my answer to that gap: it finds the shortest path from a single source to every other vertex, even in the presence of negative edge weights, and it can also tell me, definitively, whether a negative-weight cycle exists in the graph at all. I appreciate that it trades some speed for this extra robustness, and I think that trade-off is exactly why it earns its place alongside Dijkstra’s rather than being replaced by it.

History and Background

I trace the algorithm to two independent lines of work: Richard Bellman, who described the approach in 1958 as part of his broader development of dynamic programming, and Lester Ford Jr., who had described a very similar method slightly earlier, in 1956, in the context of the more general “Ford-Fulkerson” style of network flow reasoning. Edward F. Moore also contributed a related formulation around the same period, which is why some texts refer to it as the Bellman-Ford-Moore algorithm. What I find notable is that this algorithm predates Dijkstra’s own 1959 publication, making it one of the earliest formal treatments of the shortest path problem in the emerging field of algorithmic graph theory.

Problem Statement

I want to compute the shortest path distance from a single source vertex to every other vertex in a weighted, directed graph, where edge weights may be negative. Unlike the all-pairs Floyd-Warshall problem, this is a single-source problem. The presence of negative weights rules out Dijkstra’s greedy approach, since Dijkstra assumes that once a vertex’s shortest distance is finalized, it can never be improved later — an assumption that negative edges can violate. Bellman-Ford solves this more general version of the problem, and additionally detects if a negative-weight cycle reachable from the source exists, since in that case “shortest path” becomes undefined for any vertex reachable through that cycle.

Core Concepts

Relaxation: the operation of checking whether going through a given edge (u, v) with weight w offers a shorter path to v than currently known, i.e., whether dist[u] + w < dist[v], and updating dist[v] if so.
Source vertex: the starting point from which all shortest distances are measured.
Negative-weight cycle: a cycle in the graph whose total edge weight is negative, which makes shortest paths through it undefined (arbitrarily decreasing with each additional loop).
Iteration bound: Bellman-Ford performs relaxation across all edges, repeated |V| - 1 times, which is the maximum number of edges a simple shortest path can have in a graph with |V| vertices.

How It Works

I follow these steps:

I initialize the distance to the source as 0, and the distance to every other vertex as infinity.
I repeat the following relaxation step |V| - 1 times: for every edge (u, v) with weight w in the graph, if dist[u] + w < dist[v], I update dist[v] = dist[u] + w.
After |V| - 1 iterations, all shortest paths (assuming no negative cycles reachable from the source) are guaranteed to be found, since the longest possible simple shortest path uses at most |V| - 1 edges.
I perform one additional pass over all edges: if any edge can still be relaxed (i.e., dist[u] + w < dist[v] still holds), this proves a negative-weight cycle exists that is reachable from the source, and I report this instead of returning distances.

Working Principle

The mechanism relies on the fact that the shortest path between two vertices in a graph without negative cycles is always a simple path (never revisits a vertex), and a simple path can use at most |V| - 1 edges. By relaxing every edge in the graph |V| - 1 times, I guarantee that information about shortest paths propagates through the graph one “hop” per full round of relaxation — after the first pass, all shortest paths of length 1 edge are correctly found; after the second pass, all shortest paths of length up to 2 edges are correct; and so on, until after |V| - 1 passes, even the longest possible simple shortest paths are guaranteed correct. The extra V-th pass exists purely as a check: if progress is still being made, the only explanation is a negative cycle allowing paths to keep improving indefinitely.

Mathematical Foundation

I define dist_k[v] as the shortest path from the source s to vertex v using at most k edges. The recurrence is:

$$ dist_k[v] = \min\Big(dist_{k-1}[v],\ \min_{(u,v) \in E} \big(dist_{k-1}[u] + w(u,v)\big)\Big) $$

with the base case dist_0[s] = 0 and dist_0[v] = \infty for all v \neq s.

Since any simple path in a graph with |V| vertices has at most |V| - 1 edges, it follows that:

$$ dist_{|V|-1}[v] = \text{true shortest distance from } s \text{ to } v, \quad \text{for all } v, \text{ assuming no negative cycle reachable from } s $$

The total time complexity, from performing |V| - 1 full passes over all |E| edges, is:

$$ T(|V|, |E|) = O(|V| \times |E|) $$

Diagrams

flowchart TD
    A["Initialize dist[source] = 0, dist[all others] = infinity"] --> B["Repeat |V|-1 times"]
    B --> C["For each edge (u, v, w) in graph"]
    C --> D{"dist[u] + w < dist[v]?"}
    D -- Yes --> E["dist[v] = dist[u] + w"]
    D -- No --> F[No change]
    E --> G{More edges?}
    F --> G
    G -- Yes --> C
    G -- No --> H{More iterations remaining?}
    H -- Yes --> B
    H -- No --> I["One more pass over all edges"]
    I --> J{"Any edge still relaxable?"}
    J -- Yes --> K[Negative cycle detected]
    J -- No --> L[dist array holds correct shortest paths]

Pseudocode

function bellmanFord(graph, source, V, E):
    dist = array of size V, initialized to infinity
    dist[source] = 0

    for i from 1 to V - 1:
        for each edge (u, v, w) in E:
            if dist[u] != infinity and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    // Check for negative-weight cycles
    for each edge (u, v, w) in E:
        if dist[u] != infinity and dist[u] + w < dist[v]:
            return "Negative weight cycle detected"

    return dist

Step-by-Step Example

Consider a graph with vertices S, A, B, C and edges: S->A (4), S->B (5), A->B (-3), A->C (6), B->C (2), with source S.

Initialization: dist = {S: 0, A: ∞, B: ∞, C: ∞}

Iteration 1:

S->A: dist[A] = min(∞, 0+4) = 4
S->B: dist[B] = min(∞, 0+5) = 5
A->B: dist[B] = min(5, 4-3) = 1
A->C: dist[C] = min(∞, 4+6) = 10
B->C: dist[C] = min(10, 1+2) = 3

Result after iteration 1: dist = {S: 0, A: 4, B: 1, C: 3}

Iteration 2: I check all edges again; no further improvements are found, since the correct shortest distances were already reached (this can happen before |V|-1 iterations complete, though the algorithm still runs the full count to guarantee correctness in general).

Final check pass: no edge can still be relaxed, confirming no negative cycle exists.

Final distances: S: 0, A: 4, B: 1, C: 3

Time Complexity

Best case: O(|V| x |E|) — even if distances stabilize early, the standard algorithm doesn’t check for early termination by default, though this is a common optimization (see below).
Average case: O(|V| x |E|).
Worst case: O(|V| x |E|) — this is the defining cost of the algorithm, since it always performs |V| - 1 full passes over all edges.

Space Complexity

Bellman-Ford requires O(|V|) space to store the distance array. If I also want to reconstruct the actual shortest paths, I need an additional O(|V|) space for a predecessor array, which records, for each vertex, which edge most recently improved its distance. The graph itself, if represented as an edge list, requires O(|E|) space.

Correctness Analysis

I prove correctness by induction on the number of edges in the shortest path. The base case handles paths with 0 edges (just the source itself, at distance 0). For the inductive step, I assume that after k iterations, dist[v] correctly holds the shortest path distance to any vertex v reachable from the source using at most k edges. In iteration k+1, for a vertex v whose true shortest path uses exactly k+1 edges, that path can be decomposed into a shortest path of k edges to some predecessor u, followed by the edge (u, v). Since dist[u] is already correct by the inductive hypothesis, relaxing edge (u, v) during this iteration correctly updates dist[v] to the true shortest distance. Since any simple path has at most |V| - 1 edges, after |V| - 1 iterations all shortest paths (in a graph with no negative cycle reachable from the source) are guaranteed correct. The negative cycle check works because, in a graph without such a cycle, no edge can be relaxed further after |V| - 1 iterations; if some edge still relaxes on the V-th pass, it necessarily indicates a path that keeps improving indefinitely, i.e., a negative cycle.

Advantages

Correctly handles negative edge weights, unlike Dijkstra’s algorithm.
Explicitly detects the presence of negative-weight cycles reachable from the source, which is valuable information in its own right (e.g., arbitrage detection).
Simple to implement, with straightforward, uniform relaxation logic and no need for a priority queue.
Works well as a subroutine in more advanced algorithms, such as Johnson’s algorithm for all-pairs shortest paths in sparse graphs with negative weights.

Disadvantages

Significantly slower than Dijkstra’s algorithm on graphs with only non-negative weights, since it always performs O(|V| x |E|) work rather than exploiting a priority queue’s efficiency.
Doesn’t scale well to very large or dense graphs due to its higher time complexity.
Cannot compute meaningful shortest paths for vertices reachable through a negative cycle, since such paths are, by definition, unbounded below.
Requires knowledge of the full edge list up front; it isn’t naturally suited to graphs discovered incrementally or in a streaming fashion.

Applications

Routing protocols such as the historical distance-vector routing protocol RIP (Routing Information Protocol), which is directly based on the Bellman-Ford approach.
Currency arbitrage detection, where negative cycles in a graph of exchange rates (using negative logarithms of rates as edge weights) correspond to profitable arbitrage loops.
Network flow problems, where Bellman-Ford is used to find augmenting paths that may include negative-weight reduced costs, such as in the successive shortest paths algorithm for min-cost flow.
Traffic and logistics systems that must handle scenarios with cost-reducing edges (e.g., discounts or rebates modeled as negative weights).
As the core relaxation subroutine inside Johnson’s algorithm for reweighting graphs before running Dijkstra’s algorithm on each vertex.

Implementation in C

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

#define MAX_EDGES 100

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

void bellmanFord(Edge edges[], int numEdges, int numVertices, int source) {
    int dist[numVertices];

    /* Step 1: initialize distances */
    for (int i = 0; i < numVertices; i++) dist[i] = INT_MAX;
    dist[source] = 0;

    /* Step 2: relax all edges |V| - 1 times */
    for (int i = 1; i <= numVertices - 1; i++) {
        for (int j = 0; j < numEdges; j++) {
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    /* Step 3: check for negative-weight cycles */
    for (int j = 0; j < numEdges; j++) {
        int u = edges[j].u, v = edges[j].v, w = edges[j].w;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            printf("Graph contains a negative weight cycle.\n");
            return;
        }
    }

    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < numVertices; i++) {
        printf("%d\t%d\n", i, dist[i]);
    }
}

int main() {
    /* 0=S, 1=A, 2=B, 3=C */
    Edge edges[] = {
        {0, 1, 4},   /* S -> A */
        {0, 2, 5},   /* S -> B */
        {1, 2, -3},  /* A -> B */
        {1, 3, 6},   /* A -> C */
        {2, 3, 2}    /* B -> C */
    };
    int numEdges = 5;
    int numVertices = 4;

    bellmanFord(edges, numEdges, numVertices, 0);
    return 0;
}

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

#define MAX_EDGES 100

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

void bellmanFord(Edge edges[], int numEdges, int numVertices, int source) {
    int dist[numVertices];

    /* Step 1: initialize distances */
    for (int i = 0; i < numVertices; i++) dist[i] = INT_MAX;
    dist[source] = 0;

    /* Step 2: relax all edges |V| - 1 times */
    for (int i = 1; i <= numVertices - 1; i++) {
        for (int j = 0; j < numEdges; j++) {
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    /* Step 3: check for negative-weight cycles */
    for (int j = 0; j < numEdges; j++) {
        int u = edges[j].u, v = edges[j].v, w = edges[j].w;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            printf("Graph contains a negative weight cycle.\n");
            return;
        }
    }

    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < numVertices; i++) {
        printf("%d\t%d\n", i, dist[i]);
    }
}

int main() {
    /* 0=S, 1=A, 2=B, 3=C */
    Edge edges[] = {
        {0, 1, 4},   /* S -> A */
        {0, 2, 5},   /* S -> B */
        {1, 2, -3},  /* A -> B */
        {1, 3, 6},   /* A -> C */
        {2, 3, 2}    /* B -> C */
    };
    int numEdges = 5;
    int numVertices = 4;

    bellmanFord(edges, numEdges, numVertices, 0);
    return 0;
}

Sample Input and Output

Input: graph with vertices S(0), A(1), B(2), C(3) and edges S->A(4), S->B(5), A->B(-3), A->C(6), B->C(2), source S.

Output:

Vertex	Distance from Source
0	0
1	4
2	1
3	3

Optimization Techniques

Early termination: if a complete pass over all edges results in no updates at all, I can stop early, since this means all distances have already converged — no need to run the full |V| - 1 iterations in graphs that stabilize sooner.
SPFA (Shortest Path Faster Algorithm): a well-known optimization that uses a queue to only re-relax edges from vertices whose distance was just updated, often performing much better than the naive O(|V| x |E|) bound in practice, though its worst case remains the same.
Edge list ordering: processing edges in an order that roughly follows the graph’s topological structure (when possible) can reduce the number of iterations needed for convergence.
Combining with Johnson’s algorithm: when I need all-pairs shortest paths on a sparse graph with negative weights, running Bellman-Ford once to reweight edges (removing negatives) and then running Dijkstra from every vertex is far more efficient than running Bellman-Ford from every vertex individually.

Common Mistakes

Forgetting the check dist[u] != infinity before relaxing an edge, which can cause integer overflow when adding a weight to an already-infinite (very large sentinel) distance.
Running only |V| iterations of relaxation without the extra check pass, thereby failing to detect negative cycles even though the distance values themselves might look “reasonable.”
Confusing the roles of u and v when relaxing a directed edge, leading to distances being propagated in the wrong direction.
Assuming Bellman-Ford can produce meaningful shortest paths for vertices reachable through a negative cycle — those distances are fundamentally undefined and should be reported as such, not silently returned as some large negative number.

Trending Top-Read Articles

Nmap Cheat Sheet: Complete Guide to Network Scanning Commands and Options

Nmap Port Scanning Techniques: TCP SYN, Connect, UDP, ACK, FIN, and XMAS Scans Explained

Nmap Host Discovery: Ping Sweeps, ARP Scans, and Finding Live Hosts on a Network

Trending Tags

Bellman-Ford Algorithm: Working, Explanation, and Shortest Path with Negative Weights

History and Background

Problem Statement

Core Concepts

How It Works

Working Principle

Mathematical Foundation

Diagrams

Pseudocode

Step-by-Step Example

Time Complexity

Space Complexity

Correctness Analysis

Advantages

Disadvantages

Applications

Implementation in C

Sample Input and Output

Optimization Techniques

Common Mistakes

Further Reading

Like this:

Leave a ReplyCancel reply

Previous Post

Dijkstra’s Algorithm: Working, Explanation, and Shortest Path Finding

Next Post

Floyd-Warshall Algorithm: Working, Explanation, and All-Pairs Shortest Paths

Bellman-Ford Algorithm: Working, Explanation, and Shortest Path with Negative Weights

History and Background

Problem Statement

Core Concepts

How It Works

Working Principle

Mathematical Foundation

Diagrams

Pseudocode

Step-by-Step Example

Time Complexity

Space Complexity

Correctness Analysis

Advantages

Disadvantages

Applications

Implementation in C

Sample Input and Output

Optimization Techniques

Common Mistakes

Further Reading

Like this:

Leave a ReplyCancel reply

Previous Post

Next Post

Related Posts