Bellman-Ford Algorithm

Overview

The Bellman-Ford algorithm is a graph search algorithm that computes shortest paths from a single source vertex to all other vertices in a weighted directed graph. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative edge weights and can detect negative cycles.

The algorithm works by relaxing all edges repeatedly. It performs V-1 iterations (where V is the number of vertices), and in each iteration, it relaxes all edges. If after V-1 iterations, we can still relax an edge, it means there's a negative cycle in the graph.

Bellman-Ford is particularly useful in network routing protocols, currency arbitrage detection, and any scenario where negative weights are present or need to be detected.

How It Works

The algorithm follows these steps:

  1. Initialize: Set distance to source as 0, and all other distances as infinity
  2. Relax Edges: Repeat V-1 times:
    • For each edge (u, v) with weight w
    • If dist[u] + w < dist[v], update dist[v] = dist[u] + w
  3. Check for Negative Cycles: After V-1 iterations, check if any edge can still be relaxed. If yes, negative cycle exists.
  4. Result: Distances array contains shortest distances (or indicates negative cycle)

Bellman-Ford Algorithm Pseudocode


BellmanFord(graph, source):
    dist[source] = 0
    dist[v] = ∞ for all other vertices v
    parent[v] = null for all vertices
    
    // Relax edges V-1 times
    for i = 1 to V-1:
        for each edge (u, v) with weight w in graph:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
    
    // Check for negative cycles
    for each edge (u, v) with weight w in graph:
        if dist[u] + w < dist[v]:
            return "Negative cycle detected"
    
    return dist, parent

Implementation


def bellman_ford(edges, n, start):
    """
    edges: list of edges [(u, v, weight), ...]
    n:     number of vertices, passed in explicitly
    start: source vertex
    Returns: (distances, parent, has_negative_cycle)

    n MUST be a parameter. Deriving it with len(set(...)) over the edge list
    counts only vertices that appear in some edge, so any isolated vertex is
    dropped - which makes the array too short and the V-1 iteration count wrong.
    """
    dist = [float('inf')] * n
    dist[start] = 0
    parent = [-1] * n

    # Relax all edges V-1 times
    for _ in range(n - 1):
        changed = False
        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
                changed = True
        if not changed:
            break          # early exit: a pass that relaxes nothing means we are done

    # An edge still relaxable after V-1 passes implies a negative cycle
    has_negative_cycle = any(
        dist[u] != float('inf') and dist[u] + w < dist[v]
        for u, v, w in edges
    )

    return dist, parent, has_negative_cycle

def reconstruct_path(parent, target):
    """Reconstruct shortest path from parent array"""
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = parent[current]
    return path[::-1] if path[0] == target else []

Complexity Analysis

  • Time Complexity: O(V × E) where V is vertices and E is edges
  • Space Complexity: O(V) - for distance and parent arrays

The algorithm is slower than Dijkstra's (O((V + E) log V)) but can handle negative weights and detect negative cycles, which Dijkstra cannot.

Negative Cycles

A negative cycle is a cycle in the graph where the sum of edge weights is negative. If such a cycle is reachable from the source, the shortest path is undefined (can be made arbitrarily short by going around the cycle).

Bellman-Ford detects negative cycles by checking if any edge can still be relaxed after V-1 iterations. Any shortest path visits at most V-1 edges, so after V-1 passes everything should have settled; if an edge still improves, no shortest path exists.

Two cautions when a negative cycle is reported. First, the returned dist array is meaningless in that case — do not use it. Second, only cycles reachable from the source are detected. To identify which vertices are affected, run V-1 further passes and mark every vertex still being relaxed, then propagate that mark to everything reachable from them — those are the vertices whose true distance is −∞.

Note also that the algorithm assumes a directed graph. A negative-weight edge in an undirected graph is a negative cycle, since you can traverse it back and forth indefinitely.

Example

Finding shortest paths from vertex 0: 

Graph (5 vertices, one negative edge):

    0 --(4)--> 1 --(3)--> 3
    |                     ^
   (1)                    |
    |                    (-2)
    v                     |
    2 ---------------------+
    |
   (2)
    v
    4

Edges: 0->1 (4), 0->2 (1), 1->3 (3), 2->3 (-2), 2->4 (2)

V = 5, so we run V-1 = 4 relaxation passes, then a 5th checking pass.

Pass 1: relax every edge
  dist[0] = 0                       source
  dist[1] = 0 + 4    =  4           via 0->1
  dist[2] = 0 + 1    =  1           via 0->2
  dist[3] = 1 + (-2) = -1           via 2->3  (beats 4 + 3 = 7 via 1->3)
  dist[4] = 1 + 2    =  3           via 2->4

Pass 2: no edge improves -> early exit

Check pass: no edge can be relaxed -> no negative cycle

Result: dist = [0, 4, 1, -1, 3]

Note dist[4] = 3, reached as 0→2→4 at cost 1 + 2 — vertex 4 hangs off vertex 2, not vertex 3.

When to Use Bellman-Ford

Bellman-Ford is ideal when:

  • Graph has negative edge weights
  • You need to detect negative cycles
  • Graph is sparse (few edges)
  • Currency arbitrage detection
  • Network routing with negative costs

Consider alternatives when:

  • All weights are non-negative → Use Dijkstra's (faster)
  • Unweighted graph → Use BFS (simpler)
  • All-pairs shortest paths → Use Floyd-Warshall

Bellman-Ford vs Other Algorithms

Algorithm Negative Weights Time Complexity Best For
Dijkstra's No O((V + E) log V) Non-negative weights
Bellman-Ford Yes O(V × E) Negative weights, cycle detection
Floyd-Warshall Yes O(V³) All-pairs shortest paths

Real-World Applications

  • Currency Arbitrage: Detecting profitable currency exchange cycles
  • Network Routing: Routing with negative costs (e.g., refunds)
  • Game Theory: Finding optimal strategies with negative payoffs
  • Resource Allocation: Optimizing with negative costs

Related Algorithms

Explore other searching algorithms: