⚡ Bellman-Ford Fundamentals

🎯 What is the Bellman-Ford Algorithm?

Bellman-Ford is a shortest path algorithm that computes shortest paths from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra, it works with graphs that have negative edge weights and can detect negative cycles. It was developed by Richard Bellman and Lester Ford Jr. in the 1950s.

Time: O(V×E) | Space: O(V) | Handles Negative Weights: ✅ | Detects Negative Cycles: ✅

Deep Explanation

Core Insight: Bellman-Ford relaxes all edges V-1 times. After i iterations, the algorithm has found the shortest paths using at most i edges. Since a shortest path can have at most V-1 edges (no cycles), V-1 iterations are sufficient. An extra iteration detects negative cycles.

Key Intuition: The algorithm systematically overestimates distances, then repeatedly improves them by "relaxing" edges — checking if going through another vertex provides a shorter path.

📌 Dynamic Programming📌 Negative Weights OK📌 Cycle Detection📌 O(VE) Time

def bellman_ford(vertices, edges, source):
    # edges: list of (u, v, weight)
    # vertices: number of nodes (0-indexed)
    dist = [float('inf')] * vertices
    dist[source] = 0
    
    # Relax all edges V-1 times
    for _ in range(vertices - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # Early termination if no updates
    
    # Check for negative cycles
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # Negative cycle detected
    
    return dist

# Example usage
edges = [
    (0, 1, 4), (0, 2, 5), (1, 2, -2),
    (1, 3, 6), (2, 3, 1), (3, 4, 3)
]
print(bellman_ford(5, edges, 0))  # [0, 4, 2, 3, 6]

📐 Algorithm Walkthrough

🎯 Step-by-Step Example

Graph: 0→1 (4), 0→2 (5), 1→2 (-2), 1→3 (6), 2→3 (1), 3→4 (3). Source = 0.

Initialization: dist = [0, ∞, ∞, ∞, ∞]
Iteration 1: Relax 0→1: dist[1]=4, 0→2: dist[2]=5, 1→2: 4-2=2 <5 → dist[2]=2, 1→3: 4+6=10, 2→3: 2+1=3 <10 → dist[3]=3, 3→4: 3+3=6 → dist[4]=6
Iteration 2: 0→1 (no change), 0→2 (no change), 1→2: 4-2=2 (no change), 1→3: 4+6=10 >3, 2→3: 2+1=3 (no change), 3→4: 3+3=6 (no change). Done.

Why V-1 Iterations?

In a graph without negative cycles, the longest shortest path can have at most V-1 edges. After k iterations, we know shortest paths using ≤ k edges. After V-1 iterations, we have the global shortest paths.

⏱️ Time & Space Complexity

🎯 Complexity Analysis

Time Complexity: O(V × E) — V-1 iterations × E edges per iteration
Space Complexity: O(V) for distance array + O(E) to store edges
Early Termination: Can stop early if no distances update in an iteration (shown in code)
Worst-case: O(V×E) — happens when graph is dense or requires all iterations

Complexity Comparison

For dense graphs where E ≈ V², Bellman-Ford becomes O(V³) — slower than Floyd-Warshall. For sparse graphs (E ≈ V), it's O(V²), making it practical for many real-world applications.

⚠️ Handling Negative Weights

🎯 Why Bellman-Ford Works with Negatives

Unlike Dijkstra's greedy approach (which fails with negative edges), Bellman-Ford uses dynamic programming. It systematically considers all possible paths and can handle negative edges because it doesn't assume that once a node is "finalized" its distance is optimal.

Important Limitation: The graph must have no negative cycles reachable from the source. If a negative cycle exists, shortest paths are undefined (can be arbitrarily short).

# Example where Dijkstra fails but Bellman-Ford works
edges_negative = [
    (0, 1, 4), (0, 2, 5), (1, 2, -3),  # Negative edge from 1 to 2
    (2, 3, 1)
]
# Dijkstra would set dist[2]=5 (via 0→2), but correct is 4+(-3)=1
# Bellman-Ford finds correct: [0, 4, 1, 2]

🔄 Negative Cycle Detection

🎯 Identifying Negative Cycles

After V-1 relaxation iterations, run one additional iteration. If any distance can still be reduced, a negative cycle exists in the graph. This is one of Bellman-Ford's most powerful features — it's the only single-source shortest path algorithm that reliably detects negative cycles.

def detect_negative_cycle(vertices, edges, source):
    dist = [float('inf')] * vertices
    dist[source] = 0
    
    # Relax V-1 times
    for _ in range(vertices - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # Check for negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # Negative cycle found
    return False

# Graph with negative cycle: 0→1 (2), 1→2 (3), 2→0 (-10)
# This returns True

💻 Multiple Implementations

# 1. With path reconstruction
def bellman_ford_with_path(vertices, edges, source):
    dist = [float('inf')] * vertices
    prev = [-1] * vertices
    dist[source] = 0
    
    for _ in range(vertices - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    
    # Check for negative cycles
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None, None  # Negative cycle
    
    # Reconstruct path to target
    def get_path(target):
        path = []
        curr = target
        while curr != -1:
            path.append(curr)
            curr = prev[curr]
        return path[::-1]
    
    return dist, get_path

# 2. Using adjacency list for better memory
def bellman_ford_adjacency(vertices, graph, source):
    # graph: adjacency list with (neighbor, weight)
    dist = [float('inf')] * vertices
    dist[source] = 0
    
    for _ in range(vertices - 1):
        for u in range(vertices):
            if dist[u] != float('inf'):
                for v, w in graph[u]:
                    if dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w
    return dist

📊 Step-by-Step Visualization

🎯 Graph with Negative Edge

Nodes: A (source), B, C, D. Edges: A→B (3), A→C (5), B→C (1), B→D (7), C→D (-2).

Initial: dist = [A:0, B:∞, C:∞, D:∞]
Iteration 1: A→B:3, A→C:5, B→C:3+1=4 (update C:4), B→D:3+7=10, C→D:4-2=2 (update D:2)
Iteration 2: Check all edges again. A→C:5 unchanged, C→D:4-2=2 unchanged. No further updates.
Result: distances: A:0, B:3, C:4, D:2

✅ Correctness Proof & Relaxation

🎯 The Relaxation Principle

Relaxation Invariant: After i iterations, dist[v] is the length of the shortest path from source to v using at most i edges. By induction, after V-1 iterations, we have the shortest path using any number of edges (since any shortest path has at most V-1 edges without negative cycles). The algorithm is correct due to the triangle inequality property.

📈 Comparison with Dijkstra & SPFA

vs Dijkstra: Dijkstra is O((V+E)log V) but fails with negative weights. Bellman-Ford handles negative weights but is slower.
vs SPFA (Shortest Path Faster Algorithm): SPFA is a queue-optimized Bellman-Ford that averages O(E) but can degrade to O(VE). Bellman-Ford has guaranteed O(VE).
vs Floyd-Warshall: Bellman-Ford is single-source; Floyd-Warshall is all-pairs (O(V³)).
When to use Bellman-Ford: Negative edges exist, negative cycle detection needed, moderate-sized graphs.

⚡ Optimizations & SPFA

🎯 SPFA - Shortest Path Faster Algorithm

SPFA uses a queue to track which vertices' distances improved, only relaxing edges from those vertices. In practice, it's often faster than Bellman-Ford, though worst-case remains O(VE).

from collections import deque

def spfa(vertices, edges, source):
    graph = [[] for _ in range(vertices)]
    for u, v, w in edges:
        graph[u].append((v, w))
    
    dist = [float('inf')] * vertices
    in_queue = [False] * vertices
    count = [0] * vertices
    dist[source] = 0
    queue = deque([source])
    in_queue[source] = True
    
    while queue:
        u = queue.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
                    count[v] += 1
                    if count[v] >= vertices:  # Negative cycle
                        return None
    return dist

🌍 Real-World Applications

Network Routing Protocols: RIP (Routing Information Protocol) uses distance-vector routing based on Bellman-Ford.
Arbitrage Detection: Currency exchange markets - detecting negative cycles in log-weighted graphs indicates arbitrage opportunities.
Difference Constraints: Solving systems of inequalities (x₁ - x₂ ≤ c).
Minimum Mean Weight Cycle: Used in financial and scheduling problems.
GPS/Telecommunications: When negative "costs" represent benefits or discounts.

🌐 Distributed Bellman-Ford

🎯 Distance-Vector Routing

In distributed networks, each node only knows its neighbors. The distributed Bellman-Ford algorithm (used in RIP) allows nodes to compute shortest paths by exchanging distance vectors. This is fully decentralized and robust to topology changes.

🔄 Variants & Extensions

Moore-Bellman-Ford: Early termination when no updates occur.
Yen's Optimization: Process edges in a random order to potentially find solutions faster.
Dynamic Bellman-Ford: Updates after edge weight changes.
Gauss-Seidel Bellman-Ford: Uses updated values immediately within the same iteration.

💪 Practice & Problem Patterns

🎯 Classic Bellman-Ford Problems

Cheapest Flights Within K Stops (LeetCode 787): Modified Bellman-Ford with hop constraint.
Network Delay Time (LeetCode 743): Compare Dijkstra vs Bellman-Ford.
Find if there is a negative cycle (GFG): Standard detection problem.
Arbitrage (LeetCode 514): Currency exchange → log conversion → negative cycle detection.
Minimum Cost to Reach Destination with at most K edges: K-constrained shortest path.

# LeetCode 787 - Cheapest Flights Within K Stops
def findCheapestPrice(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for i in range(k + 1):
        temp = dist.copy()
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1