Day 47: Bellman-Ford Algorithm #

Welcome to Day 47 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Bellman-Ford algorithm, a versatile algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted graph.

What is the Bellman-Ford Algorithm? #

The Bellman-Ford algorithm is used to find 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 cycles in the graph.

How Does It Work? #

The algorithm works by repeatedly relaxing all edges V-1 times, where V is the number of vertices in the graph. After this process, it checks for negative-weight cycles.

1. Initialize distances from the source to all vertices as infinite and distance to the source itself as 0.
2. Relax all edges |V| - 1 times. For each edge (u, v) with weight w, if dist[v] > dist[u] + w, then update dist[v] = dist[u] + w.
3. Check for negative-weight cycles. For each edge (u, v) with weight w, if dist[v] > dist[u] + w, then there is a negative-weight cycle.

Implementing Bellman-Ford Algorithm #

Here’s an implementation of the Bellman-Ford algorithm:

 1def bellman_ford(graph, source):
 2    # Step 1: Initialize distances from source to all other vertices as INFINITE
 3    distances = {vertex: float('infinity') for vertex in graph}
 4    distances[source] = 0
 5    
 6    # Step 2: Relax all edges |V| - 1 times
 7    for _ in range(len(graph) - 1):
 8        for u in graph:
 9            for v, w in graph[u].items():
10                if distances[u] != float('infinity') and distances[u] + w < distances[v]:
11                    distances[v] = distances[u] + w
12    
13    # Step 3: Check for negative-weight cycles
14    for u in graph:
15        for v, w in graph[u].items():
16            if distances[u] != float('infinity') and distances[u] + w < distances[v]:
17                print("Graph contains negative weight cycle")
18                return None
19    
20    return distances
21
22# Example usage
23graph = {
24    'A': {'B': -1, 'C': 4},
25    'B': {'C': 3, 'D': 2, 'E': 2},
26    'C': {},
27    'D': {'B': 1, 'C': 5},
28    'E': {'D': -3}
29}
30
31source = 'A'
32distances = bellman_ford(graph, source)
33
34if distances:
35    for vertex, distance in distances.items():
36        print(f"Distance from {source} to {vertex}: {distance}")

Time and Space Complexity #

• Time Complexity: O(VE), where V is the number of vertices and E is the number of edges.
• Space Complexity: O(V) to store the distance array.

Advantages of Bellman-Ford Algorithm #

1. Can handle graphs with negative edge weights.
2. Can detect negative cycles in the graph.
3. Simpler than Dijkstra’s algorithm and doesn’t require a priority queue.

Disadvantages #

1. Slower than Dijkstra’s algorithm for graphs with non-negative edge weights.
2. Not suitable for graphs with a large number of edges and vertices due to its time complexity.

Applications of Bellman-Ford Algorithm #

1. Routing protocols in computer networks (e.g., RIP - Routing Information Protocol).
2. Finding arbitrage opportunities in currency exchange.
3. As a subroutine in other graph algorithms.

Exercise #

1. Modify the Bellman-Ford algorithm to print the actual shortest path from the source to each vertex, not just the distances.
2. Implement a function that uses the Bellman-Ford algorithm to detect if there’s a negative cycle in the graph, and if so, print the cycle.
3. Use the Bellman-Ford algorithm to solve the “Currency Arbitrage” problem: Given a table of exchange rates between currencies, find a sequence of exchanges that results in a profit.

Summary #

Today, we explored the Bellman-Ford algorithm, a versatile method for finding shortest paths in a weighted graph, even when the graph contains negative edge weights. We implemented the algorithm, discussed its time and space complexity, and looked at its advantages, disadvantages, and applications.

The Bellman-Ford algorithm is particularly useful when dealing with graphs that may contain negative edge weights or when we need to detect negative cycles in a graph.

Tomorrow, we’ll dive into the world of backtracking algorithms, starting with an introduction to the concept and some classic problems. Stay tuned!