Bellman-Ford Algorithm

July 2026 · 28 min read

Dijkstra’s algorithm is the go-to for shortest paths — until you encounter a negative-weight edge. The moment any edge has a negative cost, Dijkstra’s greedy strategy breaks: a node it marked “final” might later discover a cheaper route through the negative edge. The Bellman-Ford algorithm handles this gracefully. It is slower — O(VE) instead of O(E log V) — but it works correctly with negative weights and can detect negative-weight cycles, something Dijkstra cannot do at all. In this post we will build up the algorithm from intuition, trace it step-by-step on a graph with negative edges, add negative-cycle detection, cover the SPFA optimisation, write clean C++ code, and explore competitive-programming patterns.

When to Use Bellman-Ford

Dijkstra’s algorithm is faster, so why would you ever reach for Bellman-Ford? There are three key scenarios:

• Negative-weight edges: Real-world models often have negative costs — currency exchange profits, elevation drops, or energy gains. Dijkstra fails because it finalises a node’s distance prematurely; Bellman-Ford’s iterative relaxation handles negative weights correctly.
• Negative-cycle detection: If the graph contains a cycle whose total weight is negative, shortest paths are undefined (you can loop forever to get −∞). Bellman-Ford can detect such cycles, which is critical in arbitrage detection and constraint satisfaction.
• Shortest path with at most K edges: By running exactly K iterations (instead of V−1), Bellman-Ford finds the shortest path using at most K edges — a constraint that Dijkstra cannot enforce natively.

The Algorithm: Relax All Edges V−1 Times

Bellman-Ford is remarkably simple. It maintains a distance array dist[], initialised to ∞ for all vertices except the source (which is 0). Then it performs V−1 iterations, and in each iteration it relaxes every edge:

Why V−1 Iterations Suffice

The key insight: in a graph with V vertices, the shortest path from source to any vertex uses at most V−1 edges (assuming no negative cycles). After iteration k, Bellman-Ford has found the shortest path using at most k edges. After V−1 iterations, all shortest paths are found.

Think of it inductively:

• After iteration 1: We have the correct shortest distance for all vertices reachable via 1 edge from the source.
• After iteration 2: Correct distances for vertices reachable via ≤ 2 edges.
• After iteration k: Correct distances for vertices reachable via ≤ k edges.
• After iteration V−1: Since any simple path has at most V−1 edges, all shortest paths are finalised.

Relaxation: The Core Operation

Relaxing an edge (u, v, w) means: if going through u gives v a shorter path, update it. Formally: if dist[u] + w < dist[v], set dist[v] = dist[u] + w. Bellman-Ford simply applies this operation to every edge in every iteration, and the mathematics guarantees convergence.

Step-by-Step Walkthrough

Let’s trace Bellman-Ford on this 6-node directed graph with negative edges. Source is node 0.

Edges (processed in this order each iteration):

Detecting Negative Cycles

After V−1 iterations, Bellman-Ford has found all shortest paths — if no negative cycle exists. To check for negative cycles, we run one more iteration (the V-th pass). If any edge can still be relaxed, a negative cycle is reachable from the source.

Why Does This Work?

If there are no negative cycles, V−1 iterations are enough — all shortest paths use at most V−1 edges. If a V-th iteration still finds an improvement, it means there exists a path with V edges that is shorter, which is only possible if the path revisits a vertex — meaning it goes around a cycle, and that cycle has negative total weight.

Example: Currency Arbitrage

Imagine four currencies: USD, EUR, GBP, JPY. We model exchange rates as edge weights (using −log(rate) to convert multiplication to addition). A negative cycle means you can trade in a loop and end up with more money than you started with.

The cycle EUR → GBP → JPY → USD → EUR has total weight: (−3) + 2 + (−1) + 1 = −1. This is a negative cycle! Bellman-Ford’s V-th iteration would detect that distances keep decreasing — revealing an arbitrage opportunity.

Interactive Animation

Step through Bellman-Ford on our 6-node graph. Watch the dist[] array update as each iteration relaxes edges. Orange nodes had their distance updated in the current iteration.

SPFA: Shortest Path Faster Algorithm

The SPFA (Shortest Path Faster Algorithm) is a queue-based optimisation of Bellman-Ford. Instead of blindly relaxing all edges in every iteration, it maintains a queue of “active” vertices — vertices whose distance was recently updated and might propagate improvements.

When SPFA Helps

• Sparse graphs: On random sparse graphs, SPFA often runs in near-O(E) time because most vertices are enqueued only a few times.
• Practical speed-up: In competitive programming, SPFA is often the fastest option for shortest-path problems with negative weights, beating vanilla Bellman-Ford by a large factor.

When SPFA Fails

SPFA’s worst-case complexity is still O(VE), identical to vanilla Bellman-Ford. Problem setters who know about SPFA can construct “anti-SPFA” graphs (grid-like structures with specific edge weights) that force O(VE) behaviour. In recent competitive programming, many problems are specifically designed to break SPFA, so be cautious.

C++ Implementations

Three clean, competitive-programming-ready implementations.

1. Basic Bellman-Ford

#include <bits/stdc++.h>
using namespace std;

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

vector<long long> bellmanFord(int V, vector<Edge>& edges, int src) {
    const long long INF = 1e18;
    vector<long long> dist(V, INF);
    dist[src] = 0;

    for (int i = 0; i < V - 1; i++) {
        bool updated = false;
        for (auto& [u, v, w] : edges) {
            if (dist[u] < INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;  // early termination
    }
    return dist;
}

int main() {
    int V = 6;
    vector<Edge> edges = {
        {0,1,6}, {0,2,4}, {1,3,-1}, {2,1,-2},
        {2,3,5}, {2,4,3}, {3,5,3}, {4,3,-2}, {4,5,6}
    };

    auto dist = bellmanFord(V, edges, 0);
    for (int i = 0; i < V; i++)
        cout << "dist[" << i << "] = " << dist[i] << "\n";
    return 0;
}

Output:

dist[0] = 0
dist[1] = 2
dist[2] = 4
dist[3] = 1
dist[4] = 7
dist[5] = 4

2. Negative Cycle Detection

#include <bits/stdc++.h>
using namespace std;

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

// Returns the negative cycle as a vector, or empty if none
vector<int> findNegativeCycle(int V, vector<Edge>& edges) {
    const long long INF = 1e18;
    vector<long long> dist(V, 0);  // init to 0 to detect any cycle
    vector<int> parent(V, -1);
    int last = -1;

    for (int i = 0; i < V; i++) {
        last = -1;
        for (auto& [u, v, w] : edges) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                last = v;
            }
        }
    }

    if (last == -1) return {};  // no negative cycle

    // Trace back V steps to ensure we're inside the cycle
    int v = last;
    for (int i = 0; i < V; i++) v = parent[v];

    // Reconstruct the cycle
    vector<int> cycle;
    int cur = v;
    do {
        cycle.push_back(cur);
        cur = parent[cur];
    } while (cur != v);
    cycle.push_back(v);
    reverse(cycle.begin(), cycle.end());
    return cycle;
}

int main() {
    int V = 4;
    vector<Edge> edges = {
        {0,1,1}, {1,2,-3}, {2,3,2}, {3,1,-1}
    };
    // Cycle: 1 -> 2 -> 3 -> 1 with weight -3+2+(-1) = -2

    auto cycle = findNegativeCycle(V, edges);
    if (cycle.empty()) {
        cout << "No negative cycle\n";
    } else {
        cout << "Negative cycle: ";
        for (int v : cycle) cout << v << " ";
        cout << "\n";
    }
    return 0;
}

Output:

Negative cycle: 1 2 3 1

3. SPFA with Negative Cycle Detection

#include <bits/stdc++.h>
using namespace std;

pair<vector<long long>, bool> spfa(int V,
    vector<vector<pair<int,int>>>& adj, int src)
{
    const long long INF = 1e18;
    vector<long long> dist(V, INF);
    vector<bool> in_queue(V, false);
    vector<int> cnt(V, 0);  // enqueue count
    dist[src] = 0;

    queue<int> q;
    q.push(src);
    in_queue[src] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        in_queue[u] = false;

        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                    cnt[v]++;
                    if (cnt[v] >= V)
                        return {dist, true};  // negative cycle
                }
            }
        }
    }
    return {dist, false};
}

int main() {
    int V = 6;
    vector<vector<pair<int,int>>> adj(V);
    adj[0] = {{1,6},{2,4}};
    adj[1] = {{3,-1}};
    adj[2] = {{1,-2},{3,5},{4,3}};
    adj[3] = {{5,3}};
    adj[4] = {{3,-2},{5,6}};

    auto [dist, has_neg] = spfa(V, adj, 0);
    if (has_neg) {
        cout << "Negative cycle detected!\n";
    } else {
        for (int i = 0; i < V; i++)
            cout << "dist[" << i << "] = " << dist[i] << "\n";
    }
    return 0;
}

Output:

dist[0] = 0
dist[1] = 2
dist[2] = 4
dist[3] = 1
dist[4] = 7
dist[5] = 4

Complexity Analysis

Time Complexity

Space Complexity

All variants use O(V + E) space: O(E) for the edge list or adjacency list, plus O(V) for the dist[] and parent[] arrays. SPFA adds O(V) for the queue and in_queue[]/cnt[] arrays.

Bellman-Ford vs Dijkstra

Competitive Programming Patterns

Bellman-Ford appears in many disguises in competitive programming. Here are the most common patterns:

1. Arbitrage Detection

Given exchange rates between N currencies, determine if there is a sequence of trades that generates profit from nothing. Model currencies as nodes and −log(rate) as edge weights. A negative cycle in this graph means an arbitrage opportunity.

// Arbitrage detection with Bellman-Ford
bool hasArbitrage(int N, vector<vector<double>>& rate) {
    // rate[i][j] = exchange rate from currency i to j
    vector<double> dist(N, 0);

    for (int iter = 0; iter < N - 1; iter++)
        for (int u = 0; u < N; u++)
            for (int v = 0; v < N; v++)
                if (rate[u][v] > 0) {
                    double w = -log(rate[u][v]);
                    if (dist[u] + w < dist[v])
                        dist[v] = dist[u] + w;
                }

    // Check for negative cycle
    for (int u = 0; u < N; u++)
        for (int v = 0; v < N; v++)
            if (rate[u][v] > 0) {
                double w = -log(rate[u][v]);
                if (dist[u] + w < dist[v])
                    return true;  // arbitrage!
            }
    return false;
}

2. Shortest Path with at Most K Edges

Run Bellman-Ford for exactly K iterations instead of V−1. After iteration K, dist[v] holds the shortest path from source to v using at most K edges. Critical: to avoid using updates from the current iteration, copy the dist array at the start of each iteration.

// Shortest path from src to dst using at most K edges
long long shortestWithKEdges(int V, vector<Edge>& edges,
                              int src, int dst, int K) {
    const long long INF = 1e18;
    vector<long long> dist(V, INF);
    dist[src] = 0;

    for (int i = 0; i < K; i++) {
        vector<long long> prev = dist;  // copy!
        for (auto& [u, v, w] : edges) {
            if (prev[u] < INF && prev[u] + w < dist[v])
                dist[v] = prev[u] + w;
        }
    }
    return dist[dst];
}

This is the key idea behind LeetCode 787: Cheapest Flights Within K Stops.

3. Differential Constraints

A system of difference constraints is a set of inequalities of the form x_j − x_i ≤ w_ij. This can be modelled as a shortest-path problem: create edge i → j with weight w_ij. A feasible solution exists iff the constraint graph has no negative cycle. The shortest distances from a virtual source give a feasible assignment.

// Solve x[j] - x[i] <= w for each constraint (i, j, w)
// Returns feasible assignment or empty if impossible
vector<long long> solveDiffConstraints(int N,
    vector<tuple<int,int,int>>& constraints)
{
    // Add virtual source node N with edges to all nodes (weight 0)
    int V = N + 1, src = N;
    vector<Edge> edges;
    for (auto& [i, j, w] : constraints)
        edges.push_back({i, j, w});
    for (int i = 0; i < N; i++)
        edges.push_back({src, i, 0});

    const long long INF = 1e18;
    vector<long long> dist(V, INF);
    dist[src] = 0;

    for (int iter = 0; iter < V - 1; iter++)
        for (auto& [u, v, w] : edges)
            if (dist[u] < INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;

    // Check negative cycle
    for (auto& [u, v, w] : edges)
        if (dist[u] < INF && dist[u] + w < dist[v])
            return {};  // no feasible solution

    dist.pop_back();  // remove virtual source
    return dist;
}

Practice Problems

Test your understanding with these problems, ordered roughly by difficulty:

Summary

Let’s recap the key takeaways:

1. Core idea: Bellman-Ford relaxes all edges V−1 times. After iteration k, all shortest paths using ≤ k edges are correct.
2. Negative weights: Unlike Dijkstra, Bellman-Ford handles negative edge weights correctly because it re-examines edges multiple times.
3. Negative-cycle detection: Run one extra iteration. If any edge still relaxes, a negative cycle exists. Trace parent pointers to reconstruct it.
4. SPFA optimisation: Queue-based variant that only relaxes edges from recently-updated vertices. Average case O(E), worst case O(VE). Beware anti-SPFA test cases.
5. K-edge constraint: Run exactly K iterations (with dist copy per iteration) to find shortest paths using at most K edges.
6. Differential constraints: Systems of x_j − x_i ≤ w_ij map directly to shortest-path problems solvable by Bellman-Ford.
7. Complexity: O(VE) time, O(V+E) space. Use Dijkstra when weights are non-negative; reach for Bellman-Ford when they aren’t.