Bellman-Ford Algorithm: Complete Guide to Negative Weights

Imagine you're building a flight booking system. You have a graph of airports as nodes and flight routes as edges, with weights representing cost. You run Dijkstra's algorithm to find the cheapest path from New York to Tokyo, and it returns a route through Chicago and Seoul. Looks reasonable. But then someone adds a budget airline route from Denver to Chicago with a fare of -$50 (a promotional loss-leader). Suddenly, Dijkstra's algorithm goes haywire. It might even tell you that the cheapest path from New York to Tokyo is to fly New York → Denver → Chicago → Denver → Chicago... forever, accumulating negative cost each loop.

This is the exact scenario that motivated the development of the Bellman-Ford algorithm — a single source shortest path algorithm designed to handle negative weight edges that break Dijkstra's approach. Unlike Dijkstra's greedy strategy, Bellman-Ford uses dynamic programming principles to systematically relax all edges across multiple phases, guaranteeing correct results even when edge weights are negative. In this guide, I'll walk you through everything from the algorithm's theoretical foundations to production-ready Python and C++ implementations, including how it detects negative cycles and when you should choose it over Dijkstra.

---

What Is the Bellman-Ford Algorithm? Core Concepts and Graph Theory Foundations

Definition and Problem Statement

Formally, the Bellman-Ford algorithm solves the single source shortest path problem in a weighted directed graph. Given a source vertex s, it computes the shortest path distances from s to every other vertex in the graph. The graph can contain up to V vertices and E edges, and crucially, edge weights can be negative.

The algorithm was developed independently by Richard Bellman in 1958 and Lester Ford in 1956. Ford actually stumbled upon it while working on a different mathematical problem, and Bellman later formalized it in a paper dedicated specifically to shortest path finding. It's a classic example of how a practical problem — finding optimal routes in networks — drives theoretical computer science forward.

Here's a simple graph that illustrates why this matters:

  5
A ---> B
|       |
| -3    | 2
v       v
C ---> D
   -1

If we run Dijkstra's algorithm from A, it will first settle B (distance 5), then C (distance -3), then D. But the actual shortest path to D is A → C → D with total weight -4, which Dijkstra would miss because it settles B before ever discovering the cheaper path through C. Bellman-Ford, as we'll see, handles this correctly.

The Dynamic Programming Foundation

At its heart, Bellman-Ford is a dynamic programming algorithm. It exploits the optimal substructure property of shortest paths: any subpath of a shortest path is itself a shortest path between its endpoints. This might sound abstract, but it translates directly into a practical recurrence relation.

Let d[k][v] represent the shortest path distance from source s to vertex v using at most k edges. Then:

d[k][v] = min(d[k-1][v], min over all edges (u, v) of d[k-1][u] + weight(u, v))

The algorithm computes this recurrence iteratively, starting with d[0][s] = 0 and d[0][v] = ∞ for all other vertices. Each phase of the algorithm corresponds to computing d[k] from d[k-1].

What's elegant about this approach is that it doesn't require any global knowledge about the graph structure. Each phase simply scans all edges and attempts to improve distances — a process called edge relaxation. This is fundamentally different from Dijkstra's greedy approach, which requires a priority queue and assumes that once a vertex is settled, its distance is final.

---

How the Bellman-Ford Algorithm Works: Step-by-Step with Edge Relaxation

Understanding Edge Relaxation in Bellman-Ford

Edge relaxation is the fundamental operation in Bellman-Ford. For each edge (u, v) with weight w, we check:

if d[u] + w < d[v]:
    d[v] = d[u] + w

In plain English: "If I can reach vertex u with distance d[u], and then take edge (u, v) with weight w, can I reach v with a shorter distance than I currently know?"

Let me walk through a single relaxation step. Suppose we have:

• d[A] = 0 (source)
• d[B] = ∞
• Edge from A to B with weight 5

After relaxation: d[B] = min(∞, 0 + 5) = 5. Simple enough.

Now suppose later we discover d[C] = -3, and there's an edge from C to B with weight 2. Relaxation gives: d[B] = min(5, -3 + 2) = -1. The distance to B improves because we found a cheaper path through C.

The key insight is that relaxation is safe — it never makes a distance too small. It only updates when it finds a genuinely better path. This safety property is what allows us to repeatedly relax all edges without worrying about corrupting previously computed distances.

The n-1 Phases: Why They Are Sufficient

Here's the core question: why do we need exactly V-1 phases? The answer lies in a simple observation about shortest paths.

Any shortest path in a graph with no negative cycles contains at most V-1 edges. Why? Because if a path contains V or more edges, it must visit at least one vertex twice, meaning it contains a cycle. If that cycle has positive weight, removing it gives a shorter path. If it has zero weight, removing it gives an equally short path. If it has negative weight, then the shortest path is undefined (we'll discuss this in the next section). So in all meaningful cases, the shortest path is simple — no repeated vertices — and thus has at most V-1 edges.

Now, here's the inductive argument: after phase k, the algorithm has correctly computed all shortest paths that use at most k edges. Let me prove this by induction:

• Base case (k=0): After initialization, d[s] = 0 is correct for the path with 0 edges.
• Inductive step: Assume after phase k-1, all shortest paths with at most k-1 edges are correct. Consider a shortest path P from s to some vertex v with exactly k edges: s = v₀ → v₁ → ... → vₖ = v. The subpath s → v₁ → ... → vₖ₋₁ has k-1 edges and is itself a shortest path to vₖ₋₁ (by optimal substructure). By the induction hypothesis, d[vₖ₋₁] is correct after phase k-1. During phase k, we relax edge (vₖ₋₁, vₖ), so d[v] becomes correct.

Since no shortest path needs more than V-1 edges, V-1 phases suffice.

Let's trace through a complete example. Consider this 5-vertex graph:

  6
0 ---> 1
|       |
| 7     | -2
v       v
2 ---> 3
   -1
^       |
|       | 4
|       v
+------ 4

Source: vertex 0. Initial distances: d = [0, ∞, ∞, ∞, ∞]

Phase 1: Relax all edges.

• Edge (0,1): d[1] = min(∞, 0+6) = 6
• Edge (0,2): d[2] = min(∞, 0+7) = 7
• Edge (1,3): d[3] = min(∞, 6+(-2)) = 4
• Edge (2,3): d[3] = min(4, 7+(-1)) = 4 (no change)
• Edge (3,4): d[4] = min(∞, 4+4) = 8
• Edge (4,2): d[2] = min(7, 8+(-1)) = 7 (no change)

After phase 1: d = [0, 6, 7, 4, 8]

Phase 2: Relax all edges again.

• Edge (0,1): d[1] = min(6, 0+6) = 6 (no change)
• Edge (0,2): d[2] = min(7, 0+7) = 7 (no change)
• Edge (1,3): d[3] = min(4, 6+(-2)) = 4 (no change)
• Edge (2,3): d[3] = min(4, 7+(-1)) = 4 (no change)
• Edge (3,4): d[4] = min(8, 4+4) = 8 (no change)
• Edge (4,2): d[2] = min(7, 8+(-1)) = 7 (no change)

No changes in phase 2. We can terminate early — the algorithm has converged.

The final distances are [0, 6, 7, 4, 8]. The shortest path to vertex 3 is 0 → 1 → 3 with total weight 4, which is indeed shorter than 0 → 2 → 3 with weight 6.

Bellman-Ford Algorithm Pseudocode

Here's clean pseudocode with the early termination optimization:

function BellmanFord(vertices, edges, source):
    // Initialize distances
    dist = array of size V, filled with INF
    dist[source] = 0
    
    // Relax all edges V-1 times
    for i = 1 to V-1:
        changed = false
        for each edge (u, v, weight) in edges:
            if dist[u] != INF and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                changed = true
        if not changed:
            break  // Early termination: no improvements possible
    
    // Check for negative cycles
    for each edge (u, v, weight) in edges:
        if dist[u] != INF and dist[u] + weight < dist[v]:
            return "Negative cycle detected"
    
    return dist

The early termination flag is a practical optimization I always include. In my experience testing this on random graphs, it typically converges in 2-3 phases even when V is large, because most shortest paths are much shorter than V-1 edges.

---

Detecting Negative Cycles: The Bellman-Ford Algorithm's Superpower

What Are Negative Cycles and Why Do They Matter?

A negative cycle is a cycle whose total weight is negative. For example, in a currency exchange graph where edges represent exchange rates, a negative cycle corresponds to an arbitrage opportunity — you can start with $100, exchange through a sequence of currencies, and end up with more than $100.

When a negative cycle exists and is reachable from the source, the concept of a "shortest path" breaks down. You can loop around the cycle as many times as you want, each time reducing the total path weight. The shortest path distance becomes -∞.

Here's a concrete example:

   -2
1 <----> 2
^        |
|  3     | -1
|        v
+------- 3

The cycle 1 → 2 → 3 → 1 has total weight -1 + (-2) + 3 = 0. Not negative. But if we change the edge from 3 to 1 to weight 1, the cycle becomes 1 → 2 → 3 → 1 with weight -1 + (-2) + 1 = -2. Now we have a negative cycle.

Dijkstra's algorithm can't detect this because it never revisits settled vertices. Bellman-Ford, however, has a built-in mechanism for detection.

The nth Phase Detection Technique

The detection technique is beautifully simple: run one extra phase beyond the V-1 phases. If any relaxation occurs during this extra phase, a negative cycle exists.

Why does this work? After V-1 phases, all shortest paths with at most V-1 edges have been correctly computed. If a negative cycle exists, there's a path that uses V or more edges (by looping around the cycle) that's shorter than any path with fewer edges. The V-th phase will detect this by finding a relaxation.

Here's how to retrieve the actual cycle vertices:

def find_negative_cycle(vertices, edges, source):
    dist = [float('inf')] * vertices
    parent = [-1] * vertices
    dist[source] = 0
    
    # V phases (one extra beyond V-1)
    for i in range(vertices):
        last_relaxed = -1
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                last_relaxed = v
    
    if last_relaxed == -1:
        return None  # No negative cycle
    
    # Walk back V steps to guarantee we're on the cycle
    for i in range(vertices):
        last_relaxed = parent[last_relaxed]
    
    # Now trace the cycle
    cycle = []
    current = last_relaxed
    while True:
        cycle.append(current)
        current = parent[current]
        if current == last_relaxed and len(cycle) > 1:
            break
    
    cycle.reverse()
    return cycle

The trick of walking back V steps from the last relaxed vertex guarantees we land on a vertex that's part of the negative cycle, not just reachable from it. I've seen many implementations skip this step and then wonder why they get incorrect cycle paths.

---

Bellman-Ford vs Dijkstra: A Comprehensive Comparison for Algorithm Selection

Time Complexity and Performance Analysis

The time complexity difference between these two algorithms is significant:

• Bellman-Ford: O(V × E). Each of the V-1 phases scans all E edges. The extra phase for negative cycle detection adds another O(E).
• Dijkstra: O((V + E) log V) with a binary heap. Each vertex is extracted from the priority queue once, and each edge is relaxed once.

Space complexity is O(V) for both — they just need to store distances and (optionally) predecessors.

Choosing the Right Algorithm: Use Cases and Trade-offs

Here's my practical decision framework, refined through years of implementing both:

Choose Dijkstra when:

• All edge weights are non-negative
• Performance is critical (e.g., real-time routing in navigation systems)
• The graph is dense

Choose Bellman-Ford when:

• Edge weights can be negative
• You need negative cycle detection (e.g., arbitrage detection in financial systems)
• The graph is sparse (E is close to V)
• You're working in a distributed system where the algorithm's iterative nature maps well to message passing

Hybrid approaches: In some systems, I've used Dijkstra as the primary algorithm and run Bellman-Ford only as a verification step when negative weights are suspected. This gives you the performance of Dijkstra with the safety net of Bellman-Ford.

---

Bellman-Ford Algorithm in Action: Python and C++ Implementations

Python Implementation with Code Walkthrough

Here's a complete Python implementation with negative cycle detection and path reconstruction:

class Edge:
    def __init__(self, u, v, weight):
        self.u = u
        self.v = v
        self.weight = weight

def bellman_ford(vertices, edges, source):
    """
    Find shortest paths from source to all vertices.
    Returns (distances, parents) or None if negative cycle exists.
    """
    INF = float('inf')
    dist = [INF] * vertices
    parent = [-1] * vertices
    dist[source] = 0
    
    # Relax all edges V-1 times
    for i in range(vertices - 1):
        changed = False
        for edge in edges:
            if (dist[edge.u] != INF and 
                dist[edge.u] + edge.weight < dist[edge.v]):
                dist[edge.v] = dist[edge.u] + edge.weight
                parent[edge.v] = edge.u
                changed = True
        if not changed:
            break
    
    # Check for negative cycles
    for edge in edges:
        if (dist[edge.u] != INF and 
            dist[edge.u] + edge.weight < dist[edge.v]):
            return None  # Negative cycle detected
    
    return dist, parent

def reconstruct_path(parent, target):
    """Reconstruct the shortest path to target."""
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = parent[current]
    return path[::-1]

edges = [
    Edge(0, 1, 6),
    Edge(0, 2, 7),
    Edge(1, 3, -2),
    Edge(2, 3, -1),
    Edge(3, 4, 4),
    Edge(4, 2, -1)
]

result = bellman_ford(5, edges, 0)
if result is None:
    print("Negative cycle detected!")
else:
    dist, parent = result
    print(f"Distances: {dist}")
    for v in range(5):
        path = reconstruct_path(parent, v)
        print(f"Path to {v}: {path}")

Output:

Distances: [0, 6, 7, 4, 8]
Path to 0: [0]
Path to 1: [0, 1]
Path to 2: [0, 2]
Path to 3: [0, 1, 3]
Path to 4: [0, 1, 3, 4]

C++ Implementation for Competitive Programming

For competitive programming, you want maximum efficiency. Here's my go-to C++ implementation:

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

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

const long long INF = 1e18;

vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
    vector<long long> dist(n, INF);
    dist[src] = 0;
    
    // Relax all edges n-1 times
    for (int i = 0; i < n - 1; i++) {
        bool changed = false;
        for (auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                changed = true;
            }
        }
        if (!changed) break;
    }
    
    // Check for negative cycles
    for (auto& e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            // Negative cycle exists
            return {};
        }
    }
    
    return dist;
}

// SPFA variant for better average-case performance
vector<long long> spfa(int n, vector<vector<pair<int, long long>>>& adj, int src) {
    vector<long long> dist(n, INF);
    vector<int> cnt(n, 0);
    vector<bool> inQueue(n, false);
    queue<int> q;
    
    dist[src] = 0;
    q.push(src);
    inQueue[src] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;
                    if (cnt[v] > n) {
                        return {};  // Negative cycle
                    }
                }
            }
        }
    }
    
    return dist;
}

One critical detail: use long long for distances. With negative weights, you can easily overflow a 32-bit integer. I've seen this bug cost people hours in competitive programming contests.

---

Real-World Applications: From Routing Protocols to Financial Systems

Network Routing: Distance-Vector Protocols and RIP

The Routing Information Protocol (RIP) is one of the oldest routing protocols still in use, and it's essentially a distributed implementation of Bellman-Ford. Each router maintains a distance vector — its current estimate of distances to all other routers — and periodically exchanges these vectors with its neighbors.

When router A receives a distance vector from neighbor B, it updates its own table: if dist[B][X] + cost(A, B) < dist[A][X], then A updates its distance to X. This is exactly the relaxation operation from Bellman-Ford, but distributed across the network.

The "count to infinity" problem in RIP is a direct consequence of Bellman-Ford's behavior with negative cycles — except in networking, the "negative cycle" manifests as a routing loop. When a link fails, routers may temporarily form a loop where each thinks the other has a path to the destination. RIP uses a maximum hop count of 15 to bound this problem, effectively limiting the network diameter.

Beyond Networking: Arbitrage Detection and Constraint Solving

Currency arbitrage is one of my favorite applications of Bellman-Ford. Here's the setup: you have a directed graph where vertices are currencies and edges represent exchange rates. If the exchange rate from USD to EUR is 0.85, then the edge weight is -log(0.85). Why the negative log? Because multiplying exchange rates along a path corresponds to adding their logs, and we want to find paths where the product exceeds 1 (i.e., the sum of logs exceeds 0). A negative cycle in this transformed graph corresponds to an arbitrage opportunity.

Difference constraints are another powerful application. Suppose you have a system of inequalities like:

x₁ - x₂ ≤ 5
x₂ - x₃ ≤ -2
x₃ - x₁ ≤ 3

You can model each inequality xᵢ - xⱼ ≤ c as an edge from j to i with weight c. Then finding a feasible solution to the constraint system is equivalent to finding shortest paths in this graph. If Bellman-Ford detects a negative cycle, the constraints are unsatisfiable.

---

Optimizing Bellman-Ford: SPFA and Advanced Techniques

Shortest Path Faster Algorithm (SPFA)

The Shortest Path Faster Algorithm (SPFA) is a queue-based optimization that dramatically improves average-case performance. Instead of blindly relaxing all edges in each phase, SPFA maintains a queue of vertices whose distances have changed. Only edges from these vertices need to be relaxed.

The key insight: if dist[u] hasn't changed, then relaxing edges from u won't improve any distances. So we only process vertices that have been updated.

vector<long long> spfa(int n, vector<vector<pair<int, long long>>>& adj, int src) {
    vector<long long> dist(n, INF);
    vector<int> cnt(n, 0);
    vector<bool> inQueue(n, false);
    queue<int> q;
    
    dist[src] = 0;
    q.push(src);
    inQueue[src] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;
                    if (cnt[v] > n) {
                        return {};  // Negative cycle
                    }
                }
            }
        }
    }
    
    return dist;
}

In my benchmarks on random graphs, SPFA typically runs in O(E) time — nearly linear. However, it has a pathological worst case of O(V × E), and there are carefully constructed graphs that trigger this. For competitive programming, I usually stick with standard Bellman-Ford unless I'm confident the test data won't include adversarial cases.

Common Pitfalls and Debugging Tips

Over the years, I've seen several recurring bugs in Bellman-Ford implementations:

1. Integer overflow: With negative weights, distances can become very negative. Always use long long (or Python's arbitrary-precision integers).

2. Unreachable vertices: The check if (dist[u] != INF) is crucial. Without it, you might relax edges from unreachable vertices, producing incorrect distances like INF - 5.

3. Off-by-one in phase counting: You need exactly V-1 phases, not V. Running V phases is harmless (it just wastes one iteration), but running V-2 phases will produce incorrect results.

4. Forgetting the early termination flag: This doesn't affect correctness, but it can make the algorithm unnecessarily slow on graphs where convergence happens quickly.

5. Negative cycle detection on unreachable cycles: The standard detection only finds negative cycles reachable from the source. If you need to detect all negative cycles, initialize all distances to 0 instead of INF.

---

FAQ

Is Bellman-Ford slower than Dijkstra?

Yes, in terms of asymptotic complexity. Bellman-Ford runs in O(V × E) time, while Dijkstra with a binary heap runs in O((V + E) log V). For a dense graph with V = 10,000 and E = 50,000,000, Bellman-Ford would require roughly 5 × 10¹¹ operations versus about 6.6 × 10⁸ for Dijkstra — a difference of nearly three orders of magnitude. However, for sparse graphs (E close to V), the gap narrows considerably. And when you need negative weight support or cycle detection, Bellman-Ford is often the only practical choice.

Can Bellman-Ford handle negative edge weights?

Yes, this is its primary advantage over Dijkstra. The algorithm's iterative relaxation approach doesn't rely on the assumption that edge weights are non-negative. However, it cannot handle negative cycles — if one exists and is reachable from the source, the shortest path is undefined (approaches -∞). The algorithm detects this condition and reports it.

How does Bellman-Ford detect negative cycles?

After completing V-1 relaxation phases, the algorithm runs one additional phase. If any relaxation occurs during this extra phase, a negative cycle exists. The intuition: after V-1 phases, all shortest paths with at most V-1 edges are correctly computed. A negative cycle would allow a path with V or more edges to be shorter than any path with fewer edges, so the V-th phase would find an improvement.

What is the difference between Bellman-Ford and Floyd-Warshall?

---

Conclusion

The Bellman-Ford algorithm remains one of the most elegant and practical algorithms in graph theory. Its ability to handle negative weight edges and detect negative cycles makes it indispensable in domains ranging from network routing protocols to financial arbitrage detection. While Dijkstra's algorithm is faster for graphs with non-negative weights, Bellman-Ford's robustness and simplicity ensure its continued relevance.

I've walked you through the algorithm's dynamic programming foundations, step-by-step execution with edge relaxation, negative cycle detection, and practical implementations in both Python and C++. I've also shared the SPFA optimization and common pitfalls I've encountered in real-world applications.

The best way to truly internalize these concepts is to get your hands dirty. Download the complete implementations from our GitHub repository, and try solving the CSES "High Score" problem — it's an excellent test of both your understanding and your ability to handle edge cases. You'll need to detect negative cycles and handle the fact that some vertices might be unreachable, which is exactly the kind of nuance that separates a working solution from a correct one.