DSA Bellman-Ford Algorithm

Welcome to TheCodingCollege.com! In this post, we’ll discuss the Bellman-Ford Algorithm, a versatile algorithm for finding the shortest paths in a graph. Unlike Dijkstra’s Algorithm, Bellman-Ford can handle graphs with negative edge weights, making it suitable for a broader range of problems.

What is the Bellman-Ford Algorithm?

The Bellman-Ford Algorithm computes the shortest path from a single source to all vertices in a weighted graph. It can handle negative weight edges but not negative weight cycles, as they lead to indefinite reductions in path costs.

Key Features of the Bellman-Ford Algorithm

1. Handles Negative Weights: Unlike Dijkstra’s Algorithm, it works with negative edge weights.
2. Iterative Approach: Relaxes all edges repeatedly to find the shortest path.
3. Negative Cycle Detection: Can detect if a graph contains negative weight cycles.

Algorithm Workflow

1. Initialize distances from the source to all vertices as infinity (∞\infty) and the source distance as 0.
2. Relax all edges |V| – 1 times (where ∣V∣|V| is the number of vertices).
3. Check for negative weight cycles by performing one more relaxation iteration.

Steps of Bellman-Ford Algorithm

1. Initialization:
   • Set distance to the source as 0.
   • Set all other distances as ∞\infty.
2. Relaxation:
   • For each edge (u,v,w)(u, v, w), if distance[u]+w<distance[v]\text{distance}[u] + w < \text{distance}[v], update distance[v]\text{distance}[v].
3. Negative Cycle Detection:
   • If any edge can still be relaxed, the graph contains a negative weight cycle.

Bellman-Ford Algorithm Implementation in Python

Here’s how you can implement the Bellman-Ford Algorithm:

def bellman_ford(graph, source, vertices):
    # Step 1: Initialize distances
    distances = {i: float('inf') for i in range(vertices)}
    distances[source] = 0

    # Step 2: Relax all edges |V| - 1 times
    for _ in range(vertices - 1):
        for u, v, weight in graph:
            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 graph:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            raise ValueError("Graph contains a negative weight cycle!")

    return distances

# Example Usage
graph = [
    (0, 1, 4),  # Edge from 0 to 1 with weight 4
    (0, 2, 1),  # Edge from 0 to 2 with weight 1
    (2, 1, -2), # Edge from 2 to 1 with weight -2
    (1, 3, 2),  # Edge from 1 to 3 with weight 2
    (2, 3, 5)   # Edge from 2 to 3 with weight 5
]
vertices = 4
source = 0
try:
    distances = bellman_ford(graph, source, vertices)
    print("Shortest distances:", distances)
except ValueError as e:
    print(e)

Dry Run Example

Graph Example

• Vertices: 0,1,2,30, 1, 2, 3
• Edges:
  • (0,1,4)(0, 1, 4)
  • (0,2,1)(0, 2, 1)
  • (2,1,−2)(2, 1, -2)
  • (1,3,2)(1, 3, 2)
  • (2,3,5)(2, 3, 5)

Steps:

1. Initialization: Distances = [0,∞,∞,∞][0, \infty, \infty, \infty].
2. First Relaxation:
   • Update 11: 0+4=40 + 4 = 4.
   • Update 22: 0+1=10 + 1 = 1.
3. Second Relaxation:
   • Update 11: 1−2=−11 – 2 = -1.
   • Update 33: −1+2=1-1 + 2 = 1.
4. Third Relaxation: No updates (shortest paths finalized).
5. Negative Cycle Check: No negative weight cycles.

Final distances: [0,−1,1,1][0, -1, 1, 1].

Applications of Bellman-Ford Algorithm

1. Network Routing: Detecting issues like negative delays or loopbacks.
2. Currency Arbitrage: Identifying opportunities for profitable exchanges.
3. Shortest Path in Weighted Graphs: Particularly when negative weights are present.

Limitations

1. Negative Cycles: While the algorithm detects them, it fails to compute paths in their presence.
2. Time Complexity: Slower than Dijkstra’s Algorithm, with a complexity of O(VE)O(VE).

Bellman-Ford vs. Dijkstra

Conclusion

The Bellman-Ford Algorithm is an essential tool in the DSA toolkit, especially when dealing with graphs containing negative weights. Its ability to detect negative weight cycles adds robustness to its functionality.