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:

def bellman_ford(graph, source):
    # Step 1: Initialize distances from source to all other vertices as INFINITE
    distances = {vertex: float('infinity') for vertex in graph}
    distances[source] = 0
    
    # Step 2: Relax all edges |V| - 1 times
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, w in graph[u].items():
                if distances[u] != float('infinity') and distances[u] + w < distances[v]:
                    distances[v] = distances[u] + w
    
    # Step 3: Check for negative-weight cycles
    for u in graph:
        for v, w in graph[u].items():
            if distances[u] != float('infinity') and distances[u] + w < distances[v]:
                print("Graph contains negative weight cycle")
                return None
    
    return distances

# Example usage
graph = {
    'A': {'B': -1, 'C': 4},
    'B': {'C': 3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}

source = 'A'
distances = bellman_ford(graph, source)

if distances:
    for vertex, distance in distances.items():
        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!