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(graph, start):
    """
    graph: list of edges [(u, v, weight), ...]
    start: source vertex
    Returns: (distances, parent, has_negative_cycle)
    """
    n = len(set([u for u, _, _ in graph] + [v for _, v, _ in graph]))
    dist = [float('inf')] * n
    dist[start] = 0
    parent = [-1] * n
    
    # Relax edges V-1 times
    for _ in range(n - 1):
        for u, v, w in graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
    
    # Check for negative cycles
    has_negative_cycle = False
    for u, v, w in graph:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            has_negative_cycle = True
            break
    
    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. If an edge can be relaxed, it means we found a shorter path, which is only possible if there's a negative cycle.

Example

Finding shortest paths from vertex 0:

Graph (with negative edge):
    0 --4--> 1
    |        |
    1        3
    |        |
    v        v
    2 --(-2)--> 3
         |
         2
         |
         v
         4

Iteration 1: Relax all edges
  dist[0] = 0
  dist[1] = 4
  dist[2] = 1
  dist[3] = -1 (via 2)
  dist[4] = -1 (via 3)

Iteration 2: Relax all edges again
  dist[3] = -1 (no change)
  dist[4] = -1 (no change)

Iteration 3: Check for negative cycle
  No edge can be relaxed further
  No negative cycle detected

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

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

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:

• Dijkstra's Algorithm - For non-negative weights
• Floyd-Warshall Algorithm - All-pairs shortest paths
• A* Algorithm - Heuristic-based search
• Back to Graph Algorithms Overview