Bellman-Ford for Negative Edge Weights

The Five Concepts for Today

We will build our understanding of Bellman-Ford from the ground up:

1. The Problem with Greed: Why Dijkstra's fails and how Bellman-Ford's systematic approach provides a solution.
2. The Core Mechanic: Understanding the power of iterating $V-1$ times and relaxing every edge.
3. Detecting "Infinite Money" Glitches: How to use a $V$-th iteration to detect negative-weight cycles.
4. Python Implementation & Complexity: Writing robust code and analyzing its $O(V\cdot E)$ performance.
5. Interview Deep Dive: Contrasting Bellman-Ford with Dijkstra and discussing real-world applications like arbitrage detection.

Concept 1: The Problem with Greed & The Bellman-Ford Solution

Technical Explanation

Dijkstra's algorithm is greedy. It confidently selects the unvisited node with the smallest current distance and "locks in" its path. This assumption—that a shorter path to a finalized node will never be found—is its strength and its weakness. A negative edge can violate this assumption by creating a "detour" that ultimately results in a shorter path to a node that Dijkstra's has already finalized.

Bellman-Ford's approach is fundamentally different and more methodical. Instead of making a greedy choice, it systematically relaxes every single edge in the graph over and over again. This brute-force patience ensures that the "cheaper" paths created by negative edges are eventually discovered and propagated through the graph. It doesn't commit to a path prematurely.

To see why Dijkstra's fails and to get a first look at Bellman-Ford, the following video provides an excellent introduction.

Metaphor: The Patient Travel Agent vs. The Eager Backpacker

Dijkstra's algorithm is like an eager backpacker who arrives in a new city and immediately takes the bus that promises the quickest route to the first landmark. They never look back, assuming they made the best choice.

Bellman-Ford is like a patient, methodical travel agent planning a multi-city trip. The agent re-evaluates the entire itinerary from start to finish every day for a week. On Monday, a direct flight might be cheapest. But on Tuesday, a new deal appears: a flight to a different city with a connecting train ride is now cheaper overall. Because the agent re-checks everything repeatedly, they will find this optimal, non-obvious route. Bellman-Ford's repeated iterations are like the agent's daily re-evaluations.

Concept 2: The Core Mechanic - Iterative Relaxation

Technical Explanation

The engine of the Bellman-Ford algorithm is simple yet powerful. It consists of two main phases:

1. Initialization:

   • Create a distance array, dist, of size $V$ (the number of vertices).
   • Set the distance to the source node dist[s] to 0.
   • Set all other distances dist[v] to infinity ($\infty$).

2. Relaxation Rounds:

   • Repeat $V-1$ times:
     • For every edge $(u,v)$ with weight $w$ in the graph:
       • Perform the relaxation step: if dist[u] + w < dist[v], then update dist[v] = dist[u] + w.

The key question is: Why $V-1$ iterations? A simple path in a graph (one that doesn't repeat vertices) can have at most $V-1$ edges. In the worst-case scenario, the shortest path information propagates from the source one edge at a time per iteration. After 1 iteration, Bellman-Ford guarantees to find the shortest path of at most 1 edge. After $k$ iterations, it guarantees to find the shortest path of at most $k$ edges. Therefore, after $V-1$ iterations, it guarantees to find all shortest simple paths.

This process is visualized clearly in the image below, showing how distances are updated iteration by iteration.

# The core relaxation logic of Bellman-Ford
# Assume 'distances' is initialized, 'edges' is a list of [u, v, weight]
# and 'num_nodes' is V.

for i in range(num_nodes - 1):
    # In each of the V-1 rounds, iterate over all E edges
    for u, v, weight in edges:
        # If we found a shorter path to v through u...
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            # ...update it.
            distances[v] = distances[u] + weight

Concept 3: Detecting Negative-Weight Cycles

Technical Explanation

This is Bellman-Ford's most powerful feature. After $V-1$ iterations, all shortest simple paths have been found. If we run the relaxation loop one more time—a $V$-th iteration—and we are still able to relax an edge, it means we've found a path that has become even shorter. This is only possible if the path contains a negative-weight cycle.

A negative-weight cycle is a loop in the graph where the sum of the edge weights is negative. If such a cycle is reachable from the source, you could traverse it infinitely, decreasing the path cost each time. In this case, the shortest path is undefined (it's $-\infty$). Bellman-Ford elegantly detects this by checking for any possible improvements after the algorithm should have already converged.

Metaphor: The Infinite Money Glitch

Imagine a network of international currency exchange booths. The nodes are currencies (USD, EUR, JPY) and the directed edge weights represent the cost/gain of an exchange transaction. A negative-weight cycle is an arbitrage opportunity: a sequence of trades (e.g., USD → EUR → JPY → USD) that leaves you with more money than you started with. You could repeat this loop forever, generating infinite profit.

Bellman-Ford's $V$-th iteration is like an auditor checking the books. After all legitimate transactions should have settled (after $V-1$ rounds), the auditor does one final check. If they find that someone's account balance can still be improved, they know there's a "money glitch" or arbitrage loop in the system.

# The negative cycle detection logic

# This loop runs after the main V-1 relaxation rounds
for u, v, weight in edges:
    if distances[u] != float('inf') and distances[u] + weight < distances[v]:
        # If we can still relax an edge, a negative cycle exists.
        # The path to 'v' and any node reachable from it is -infinity.
        raise ValueError("Graph contains a negative-weight cycle")

Concept 4: Full Python Implementation & Complexity Analysis

Technical Explanation

Now, let's assemble the pieces into a single, robust Python function. For Bellman-Ford, it's often most convenient to represent the graph as a simple list of edges, rather than an adjacency list, as the algorithm must iterate through every edge anyway.

Here is a Python implementation that reflects best practices. It takes an edge list, the number of nodes, and the source as input.

def bellman_ford(edges: list[list[int]], num_nodes: int, source: int):
    """
    Implements the Bellman-Ford algorithm to find the shortest paths from a
    source node in a weighted graph, and detects negative-weight cycles.

    Args:
        edges: A list of edges, where each edge is [u, v, weight].
        num_nodes: The total number of nodes (V).
        source: The starting node.

    Returns:
        A dictionary mapping each node to its shortest distance from the source.

    Raises:
        ValueError: If the graph contains a negative-weight cycle.
    """
    # Step 1: Initialize distances
    distances = {node: float('inf') for node in range(num_nodes)}
    distances[source] = 0

    # Step 2: Relax edges |V| - 1 times
    for _ in range(num_nodes - 1):
        # A temporary copy to check for convergence
        # In practice, you often just run the loop without this optimization
        # as the V-th iteration is needed for cycle detection.
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
    
    # Step 3: Check for negative-weight cycles
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            raise ValueError("Graph contains a negative-weight cycle")
            
    return distances

# --- Example Usage ---
# Graph with a negative edge but no negative cycle
num_nodes_ex1 = 5
edges_ex1 = [[0, 1, -1], [0, 2, 4], [1, 2, 3], [1, 3, 2], [1, 4, 2], [3, 2, 5], [3, 1, 1], [4, 3, -3]]
source_node = 0
print(f"Graph 1 Shortest Paths: {bellman_ford(edges_ex1, num_nodes_ex1, source_node)}")
# Expected: {0: 0, 1: -1, 2: 2, 3: -2, 4: 1}

# Graph with a negative cycle
num_nodes_ex2 = 3
edges_ex2 = [[0, 1, 1], [1, 2, -2], [2, 1, -2]]
try:
    bellman_ford(edges_ex2, num_nodes_ex2, source_node)
except ValueError as e:
    print(f"Graph 2 Test: Caught expected error -> {e}")
# Expected: Caught expected error -> Graph contains a negative-weight cycle

Complexity Analysis

• Time Complexity: $O(V\cdot E)$

  • The main relaxation phase consists of a loop that runs $V-1$ times. Inside this loop, we iterate through all $E$ edges. This gives $O(V\cdot E)$.
  • The negative cycle detection phase is one more pass through all $E$ edges, which is $O(E)$.
  • The total complexity is $O(V\cdot E+E)=O(V\cdot E)$. This is slower than Dijkstra's $O(E\log V)$ but is the price of handling negative weights.

• Space Complexity: $O(V)$

  • We need to store the distances for each of the $V$ vertices. If we were also reconstructing the path, we would need an additional predecessor array of size $V$. The space required is dominated by these arrays.

Concept 5: Interview Deep Dive - Trade-offs & Applications

Technical Explanation

In an interview at a company like Google or Meta, you will be expected to articulate the trade-offs between algorithms. The Dijkstra vs. Bellman-Ford question is a classic.

When to use which?

• Use Dijkstra's when you can guarantee edge weights are non-negative (e.g., physical distance, time, network latency). It is significantly faster.
• Use Bellman-Ford when edge weights can be negative (e.g., financial gains/losses, discounts, arbitrage) or when you explicitly need to check for the existence of negative cycles.

One of the most cited real-world applications is arbitrage detection in currency markets, as described in our metaphor. Early distance-vector routing protocols in networking, like the Routing Information Protocol (RIP), also used principles similar to Bellman-Ford.

Conclusion

Today you've added a critical and robust tool to your algorithmic arsenal. While slower than Dijkstra's, Bellman-Ford's ability to handle negative weights and detect negative cycles makes it invaluable for a whole class of problems that Dijkstra's cannot solve.

Key Takeaways:

• Bellman-Ford solves the SSSP problem for graphs that may contain negative edge weights.
• Its core mechanic involves relaxing all $E$ edges for $V-1$ rounds.
• A final, $V$-th round of relaxations is used to detect negative-weight cycles.
• The time complexity is $O(V\cdot E)$, making it slower than Dijkstra's but more versatile.
• It is the go-to algorithm for problems involving potential gains/losses, like arbitrage detection.

Preview of the Next Lesson:
We have now thoroughly covered single-source shortest paths. Next, we will pivot to a different but equally important graph problem: finding the Minimum Spanning Tree (MST). Instead of finding the shortest path between two points, an MST finds the cheapest way to connect all nodes in a graph. We will learn two classic greedy algorithms for this: Kruskal's and Prim's.