Bellman-Ford Algorithm

The Bellman-Ford algorithm is a single-source shortest path algorithm that can handle graphs with negative edge weights. Unlike Dijkstra’s algorithm, it can detect negative cycles, which are cycles where the sum of edge weights is negative.

Key Concepts

• Relaxation: The core operation where the estimated shortest distance to a vertex is updated if a shorter path is found.
• Negative Cycle: A cycle in a graph where the sum of edge weights is negative. If a negative cycle is reachable from the source, shortest paths are not well-defined.

Algorithm Steps

1. Initialization:

   • Initialize distances: Set the distance to the source vertex as 0 and all other vertices as infinity.

2. Relaxation (V-1 times):

   • Repeat V-1 times (where V is the number of vertices):
     • For each edge (u, v) with weight w in the graph:
       • If dist[u] + w < dist[v]:
         • Update dist[v] = dist[u] + w.

3. Negative Cycle Detection:

   • After V-1 iterations, perform one more iteration over all edges.
   • If any distance dist[v] is updated (i.e., dist[u] + w < dist[v]), it indicates the presence of a negative cycle reachable from the source.

Time and Space Complexity

• Time Complexity: O(V * E), where V is the number of vertices and E is the number of edges. This is because the algorithm iterates V-1 times, and in each iteration, it relaxes all E edges.
• Space Complexity: O(V) for storing distances.

Python Code Example

def bellman_ford(graph, start_node):
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0

    # Relax edges V-1 times
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u].items():
                if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight

    # Check for negative cycles
    for u in graph:
        for v, weight in graph[u].items():
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                print("Graph contains negative cycle!")
                return None  # Indicates negative cycle

    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}
}

start_node = 'A'
shortest_paths = bellman_ford(graph, start_node)

if shortest_paths:
    print(f"Shortest paths from {start_node}: {shortest_paths}")

# Example with negative cycle
graph_with_cycle = {
    'A': {'B': 1},
    'B': {'C': -1},
    'C': {'A': -1}
}

print("\nTesting graph with negative cycle:")
bellman_ford(graph_with_cycle, 'A')