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.

Solution#

 1# Exercise 1: Bellman-Ford that reconstructs the actual shortest path.
 2# We track a predecessor for each vertex during relaxation.
 3def bellman_ford_paths(graph, source):
 4    distances = {v: float('inf') for v in graph}
 5    predecessor = {v: None for v in graph}
 6    distances[source] = 0
 7
 8    for _ in range(len(graph) - 1):
 9        for u in graph:
10            for v, w in graph[u].items():
11                if distances[u] != float('inf') and distances[u] + w < distances[v]:
12                    distances[v] = distances[u] + w
13                    predecessor[v] = u
14
15    # Negative cycle check: if we can still relax, a cycle exists.
16    for u in graph:
17        for v, w in graph[u].items():
18            if distances[u] != float('inf') and distances[u] + w < distances[v]:
19                raise ValueError("Graph contains a negative weight cycle")
20
21    def build_path(target):
22        path = []
23        while target is not None:
24            path.append(target)
25            target = predecessor[target]
26        return path[::-1]
27
28    return {v: build_path(v) for v in graph}, distances
29
30graph = {
31    'A': {'B': -1, 'C': 4},
32    'B': {'C': 3, 'D': 2, 'E': 2},
33    'C': {},
34    'D': {'B': 1, 'C': 5},
35    'E': {'D': -3},
36}
37paths, dist = bellman_ford_paths(graph, 'A')
38for v in graph:
39    print(v, dist[v], paths[v])

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