Bellman-Ford Algorithm

Find shortest paths from a source vertex to all other vertices in a weighted graph, capable of handling negative edge weights

Language Selection

Choose your preferred programming language

Showing: Python

Bellman-Ford Algorithm

Problem Statement

The Bellman-Ford algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph. Unlike Dijkstra’s algorithm, Bellman-Ford can handle graphs with negative edge weights and can detect negative weight cycles.

Input/Output Specifications

Input:
- A weighted directed graph represented as edges [u, v, weight]
- Number of vertices n
- Source vertex src
Output:
- An array of shortest distances from source to all vertices
- null/false if a negative cycle is detected

Constraints

1 <= n <= 100 (number of vertices)
0 <= edges.length <= 6000
edges[i] = [ui, vi, weighti] where ui != vi
-100 <= weighti <= 100
0 <= src < n

Examples

Example 1:

Input: n = 3, edges = [[0,1,1],[1,2,3],[0,2,4]], src = 0
Output: [0, 1, 4]
Explanation: 
- Distance from 0 to 0: 0
- Distance from 0 to 1: 1 (via edge 0->1)
- Distance from 0 to 2: 4 (via path 0->1->2 with cost 1+3=4, shorter than direct edge 0->2 with cost 4)

Example 2:

Input: n = 4, edges = [[0,1,1],[1,2,-3],[2,3,1],[3,1,1]], src = 0
Output: null
Explanation: There's a negative cycle: 1->2->3->1 with total weight -1

Example 3:

Input: n = 2, edges = [[0,1,-1]], src = 0
Output: [0, -1]
Explanation: Shortest path from 0 to 1 has cost -1 (negative weight allowed)

Solution Approaches

Approach 1: Standard Bellman-Ford Algorithm

Algorithm Explanation:

Initialize distances: Set distance to source as 0, all others as infinity
Relax edges: For (V-1) iterations, relax all edges
Detect negative cycles: Run one more iteration; if any distance decreases, there’s a negative cycle
Relaxation: For edge (u,v) with weight w, if dist[u] + w < dist[v], update dist[v]

Implementation:

Python:

def bellman_ford(n, edges, src):
    """
    Bellman-Ford algorithm for shortest paths with negative edge detection
    Time: O(VE)
    Space: O(V)
    """
    # Initialize distances
    dist = [float('inf')] * n
    dist[src] = 0
    
    # Relax edges V-1 times
    for _ in range(n - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    
    # Check for negative cycles
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return None  # Negative cycle detected
    
    return dist

def bellman_ford_optimized(n, edges, src):
    """
    Optimized Bellman-Ford with early termination
    Time: O(VE) worst case, O(E) best case
    Space: O(V)
    """
    dist = [float('inf')] * n
    dist[src] = 0
    
    # Relax edges with early termination
    for iteration in range(n - 1):
        updated = False
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                updated = True
        
        # Early termination if no updates
        if not updated:
            break
    
    # Check for negative cycles
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return None
    
    return dist

Java:

class Solution {
    /**
     * Bellman-Ford algorithm for shortest paths
     * Time: O(VE)
     * Space: O(V)
     */
    public int[] bellmanFord(int n, int[][] edges, int src) {
        // Initialize distances
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < n - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], weight = edge[2];
                if (dist[u] != Integer.MAX_VALUE && 
                    dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
        
        // Check for negative cycles
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            if (dist[u] != Integer.MAX_VALUE && 
                dist[u] + weight < dist[v]) {
                return null; // Negative cycle detected
            }
        }
        
        return dist;
    }
    
    /**
     * Optimized Bellman-Ford with early termination
     */
    public int[] bellmanFordOptimized(int n, int[][] edges, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], weight = edge[2];
                if (dist[u] != Integer.MAX_VALUE && 
                    dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    updated = true;
                }
            }
            if (!updated) break; // Early termination
        }
        
        // Check for negative cycles
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            if (dist[u] != Integer.MAX_VALUE && 
                dist[u] + weight < dist[v]) {
                return null;
            }
        }
        
        return dist;
    }
}

Go:

// bellmanFord - Standard Bellman-Ford algorithm
// Time: O(VE)
// Space: O(V)
func bellmanFord(n int, edges [][]int, src int) []int {
    // Initialize distances
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[src] = 0
    
    // Relax edges V-1 times
    for i := 0; i < n-1; i++ {
        for _, edge := range edges {
            u, v, weight := edge[0], edge[1], edge[2]
            if dist[u] != math.MaxInt32 && dist[u]+weight < dist[v] {
                dist[v] = dist[u] + weight
            }
        }
    }
    
    // Check for negative cycles
    for _, edge := range edges {
        u, v, weight := edge[0], edge[1], edge[2]
        if dist[u] != math.MaxInt32 && dist[u]+weight < dist[v] {
            return nil // Negative cycle detected
        }
    }
    
    return dist
}

// bellmanFordOptimized - Optimized with early termination
func bellmanFordOptimized(n int, edges [][]int, src int) []int {
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[src] = 0
    
    for i := 0; i < n-1; i++ {
        updated := false
        for _, edge := range edges {
            u, v, weight := edge[0], edge[1], edge[2]
            if dist[u] != math.MaxInt32 && dist[u]+weight < dist[v] {
                dist[v] = dist[u] + weight
                updated = true
            }
        }
        if !updated {
            break // Early termination
        }
    }
    
    // Check for negative cycles
    for _, edge := range edges {
        u, v, weight := edge[0], edge[1], edge[2]
        if dist[u] != math.MaxInt32 && dist[u]+weight < dist[v] {
            return nil
        }
    }
    
    return dist
}

JavaScript:

/**
 * Bellman-Ford algorithm for shortest paths
 * Time: O(VE)
 * Space: O(V)
 */
function bellmanFord(n, edges, src) {
    // Initialize distances
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    
    // Relax edges V-1 times
    for (let i = 0; i < n - 1; i++) {
        for (const [u, v, weight] of edges) {
            if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    
    // Check for negative cycles
    for (const [u, v, weight] of edges) {
        if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
            return null; // Negative cycle detected
        }
    }
    
    return dist;
}

/**
 * Optimized Bellman-Ford with early termination
 */
function bellmanFordOptimized(n, edges, src) {
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    
    for (let i = 0; i < n - 1; i++) {
        let updated = false;
        for (const [u, v, weight] of edges) {
            if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                updated = true;
            }
        }
        if (!updated) break; // Early termination
    }
    
    // Check for negative cycles
    for (const [u, v, weight] of edges) {
        if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
            return null;
        }
    }
    
    return dist;
}

// Alternative using ES6 destructuring and arrow functions
const bellmanFordES6 = (n, edges, src) => {
    const dist = Array(n).fill(Infinity);
    dist[src] = 0;
    
    // Relax edges
    for (let i = 0; i < n - 1; i++) {
        edges.forEach(([u, v, weight]) => {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        });
    }
    
    // Detect negative cycles
    return edges.some(([u, v, weight]) => dist[u] + weight < dist[v]) 
        ? null : dist;
};

C#:

public class Solution {
    /// <summary>
    /// Bellman-Ford algorithm for shortest paths
    /// Time: O(VE)
    /// Space: O(V)
    /// </summary>
    public int[] BellmanFord(int n, int[][] edges, int src) {
        // Initialize distances
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[src] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < n - 1; i++) {
            foreach (var edge in edges) {
                int u = edge[0], v = edge[1], weight = edge[2];
                if (dist[u] != int.MaxValue && 
                    dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
        
        // Check for negative cycles
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            if (dist[u] != int.MaxValue && 
                dist[u] + weight < dist[v]) {
                return null; // Negative cycle detected
            }
        }
        
        return dist;
    }
    
    /// <summary>
    /// Optimized Bellman-Ford with LINQ and early termination
    /// </summary>
    public int[] BellmanFordLinq(int n, int[][] edges, int src) {
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[src] = 0;
        
        for (int i = 0; i < n - 1; i++) {
            bool updated = false;
            
            foreach (var edge in edges) {
                int u = edge[0], v = edge[1], weight = edge[2];
                if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    updated = true;
                }
            }
            
            if (!updated) break;
        }
        
        // Check for negative cycles using LINQ
        bool hasNegativeCycle = edges.Any(edge => {
            int u = edge[0], v = edge[1], weight = edge[2];
            return dist[u] != int.MaxValue && dist[u] + weight < dist[v];
        });
        
        return hasNegativeCycle ? null : dist;
    }
}

Complexity Analysis:

Time Complexity: O(VE) where V is vertices and E is edges
Space Complexity: O(V) for the distance array

Trade-offs:

Can handle negative edge weights (unlike Dijkstra)
Detects negative cycles
Slower than Dijkstra for non-negative weights
Simple implementation and easy to understand

Approach 2: SPFA (Shortest Path Faster Algorithm)

Algorithm Explanation: SPFA is an optimization of Bellman-Ford that uses a queue to only relax edges from vertices whose distance was recently updated.

Implementation:

Python:

from collections import deque

def spfa(n, edges, src):
    """
    SPFA algorithm - optimized Bellman-Ford
    Time: O(VE) worst case, O(E) average case
    Space: O(V + E)
    """
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v, weight in edges:
        graph[u].append((v, weight))
    
    dist = [float('inf')] * n
    dist[src] = 0
    
    queue = deque([src])
    in_queue = [False] * n
    in_queue[src] = True
    count = [0] * n  # Count of times each vertex is relaxed
    
    while queue:
        u = queue.popleft()
        in_queue[u] = False
        
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                count[v] += 1
                
                # Negative cycle detection
                if count[v] >= n:
                    return None
                
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
    
    return dist

Java:

class Solution {
    /**
     * SPFA algorithm - optimized Bellman-Ford
     * Time: O(VE) worst case, O(E) average case
     * Space: O(V + E)
     */
    public int[] spfa(int n, int[][] edges, int src) {
        // Build adjacency list
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        Queue<Integer> queue = new LinkedList<>();
        boolean[] inQueue = new boolean[n];
        int[] count = new int[n];
        
        queue.offer(src);
        inQueue[src] = true;
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;
            
            for (int[] neighbor : graph.get(u)) {
                int v = neighbor[0], weight = neighbor[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    count[v]++;
                    
                    if (count[v] >= n) {
                        return null; // Negative cycle
                    }
                    
                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        
        return dist;
    }
}

Go:

// spfa - SPFA algorithm implementation
// Time: O(VE) worst case, O(E) average case
// Space: O(V + E)
func spfa(n int, edges [][]int, src int) []int {
    // Build adjacency list
    graph := make([][][2]int, n)
    for _, edge := range edges {
        u, v, weight := edge[0], edge[1], edge[2]
        graph[u] = append(graph[u], [2]int{v, weight})
    }
    
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[src] = 0
    
    queue := []int{src}
    inQueue := make([]bool, n)
    inQueue[src] = true
    count := make([]int, n)
    
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        inQueue[u] = false
        
        for _, neighbor := range graph[u] {
            v, weight := neighbor[0], neighbor[1]
            if dist[u]+weight < dist[v] {
                dist[v] = dist[u] + weight
                count[v]++
                
                if count[v] >= n {
                    return nil // Negative cycle
                }
                
                if !inQueue[v] {
                    queue = append(queue, v)
                    inQueue[v] = true
                }
            }
        }
    }
    
    return dist
}

JavaScript:

/**
 * SPFA algorithm - optimized Bellman-Ford
 * Time: O(VE) worst case, O(E) average case
 * Space: O(V + E)
 */
function spfa(n, edges, src) {
    // Build adjacency list
    const graph = Array.from({length: n}, () => []);
    for (const [u, v, weight] of edges) {
        graph[u].push([v, weight]);
    }
    
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    
    const queue = [src];
    const inQueue = new Array(n).fill(false);
    inQueue[src] = true;
    const count = new Array(n).fill(0);
    
    while (queue.length > 0) {
        const u = queue.shift();
        inQueue[u] = false;
        
        for (const [v, weight] of graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                count[v]++;
                
                if (count[v] >= n) {
                    return null; // Negative cycle
                }
                
                if (!inQueue[v]) {
                    queue.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    
    return dist;
}

C#:

public class Solution {
    /// <summary>
    /// SPFA algorithm - optimized Bellman-Ford
    /// Time: O(VE) worst case, O(E) average case
    /// Space: O(V + E)
    /// </summary>
    public int[] Spfa(int n, int[][] edges, int src) {
        // Build adjacency list
        var graph = new List<List<(int v, int weight)>>();
        for (int i = 0; i < n; i++) {
            graph.Add(new List<(int, int)>());
        }
        foreach (var edge in edges) {
            graph[edge[0]].Add((edge[1], edge[2]));
        }
        
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[src] = 0;
        
        var queue = new Queue<int>();
        bool[] inQueue = new bool[n];
        int[] count = new int[n];
        
        queue.Enqueue(src);
        inQueue[src] = true;
        
        while (queue.Count > 0) {
            int u = queue.Dequeue();
            inQueue[u] = false;
            
            foreach (var (v, weight) in graph[u]) {
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    count[v]++;
                    
                    if (count[v] >= n) {
                        return null; // Negative cycle
                    }
                    
                    if (!inQueue[v]) {
                        queue.Enqueue(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        
        return dist;
    }
}

Complexity Analysis:

Time Complexity: O(VE) worst case, O(E) average case
Space Complexity: O(V + E) for adjacency list and auxiliary arrays

Trade-offs:

Generally faster than standard Bellman-Ford in practice
Better performance on sparse graphs
Still detects negative cycles
More complex implementation

Key Insights

Why Bellman-Ford works: Uses dynamic programming principle - optimal substructure
Negative cycle detection: If we can still improve distances after V-1 iterations, there’s a negative cycle
When to use: When graph has negative edges or need negative cycle detection
Relaxation order: Unlike Dijkstra, order doesn’t matter for correctness
V-1 iterations: Maximum shortest path has at most V-1 edges (no cycles)

Edge Cases

Single vertex: n=1 → Distance array [0]
No edges: Disconnected graph → Only source has distance 0, others infinity
Self loops: Negative self-loop creates negative cycle
Negative cycle: Algorithm detects and returns null/false
All negative weights: Algorithm handles correctly
Unreachable vertices: Remain at infinity distance

How Solutions Handle Edge Cases:

Single vertex: Algorithm works with empty edge list
No edges: Only source distance is updated
Self loops: Detected in negative cycle check
Negative cycles: Explicit detection and early return
Unreachable vertices: Distance remains infinity

Test Cases

def test_bellman_ford():
    # Basic shortest path
    assert bellman_ford(3, [[0,1,1],[1,2,3],[0,2,4]], 0) == [0, 1, 4]
    
    # Negative weights
    assert bellman_ford(2, [[0,1,-1]], 0) == [0, -1]
    
    # Negative cycle
    assert bellman_ford(4, [[0,1,1],[1,2,-3],[2,3,1],[3,1,1]], 0) is None
    
    # Single vertex
    assert bellman_ford(1, [], 0) == [0]
    
    # Disconnected graph
    assert bellman_ford(3, [[0,1,1]], 0) == [0, 1, float('inf')]
    
    # Multiple paths
    edges = [[0,1,4],[0,2,2],[1,2,-3],[2,3,2],[1,3,5]]
    assert bellman_ford(4, edges, 0) == [0, 4, 1, 3]
    
    print("All tests passed!")

test_bellman_ford()

Follow-up Questions

Detect all vertices in negative cycles: How would you find all vertices affected by negative cycles?
Path reconstruction: How would you modify the algorithm to return actual paths?
All-pairs shortest paths: How does this compare to Floyd-Warshall?
Parallel implementation: How could you parallelize Bellman-Ford?
Online version: How would you handle dynamic edge updates?

Common Mistakes

Wrong infinity representation: Using Integer.MIN_VALUE can cause overflow
- Problem: Addition operations may overflow
- Solution: Use Integer.MAX_VALUE or language-specific infinity
Incorrect cycle detection: Forgetting to check if source is reachable
- Problem: False positive cycle detection
- Solution: Only relax edges from reachable vertices
Off-by-one in iterations: Running V iterations instead of V-1
- Problem: May miss optimal solutions
- Solution: Relax exactly V-1 times, then check for cycles
Path reconstruction errors: Not storing predecessor information
- Problem: Cannot reconstruct actual shortest paths
- Solution: Maintain predecessor array during relaxation

Interview Tips

Start with explanation: Explain why V-1 iterations are sufficient
Mention negative cycles: Always discuss cycle detection capability
Compare with Dijkstra: Highlight when to use each algorithm
Discuss optimizations: Mention SPFA and early termination
Edge case awareness: Show understanding of graph connectivity issues

Concept Explanations

Dynamic Programming on Graphs: Bellman-Ford uses the principle that the shortest path from source to any vertex using at most k edges can be computed from shortest paths using at most k-1 edges.

Relaxation Process: The key operation is edge relaxation - checking if going through an edge provides a shorter path and updating accordingly.

When to Apply: Use Bellman-Ford when you need shortest paths with negative edge weights, need to detect negative cycles, or when the graph is dense and Dijkstra’s advantage is minimal.