Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network. It was developed by Jack Edmonds and Richard Karp in 1972. The key difference between the Edmonds-Karp algorithm and the general Ford-Fulkerson method is that it uses breadth-first search (BFS) to find augmenting paths, ensuring that the shortest path (in terms of number of edges) is always chosen. This results in a more predictable running time compared to the general Ford-Fulkerson method.

Overview

The Edmonds-Karp algorithm operates on a flow network, which consists of:

• A set of vertices \( V \).
• A set of directed edges \( E \), each with a capacity \( c(u, v) \geq 0 \).
• A source vertex \( s \).
• A sink vertex \( t \).

The goal is to find the maximum amount of flow that can be sent from the source \( s \) to the sink \( t \) without exceeding the capacities of the edges.

Algorithm Steps

1. Initialization: Set the flow in all edges to zero.
2. Augmenting Path Search: Use BFS to find an augmenting path from the source \( s \) to the sink \( t \). An augmenting path is a path where the residual capacity (capacity minus current flow) of every edge is positive.
3. Flow Augmentation: If an augmenting path is found, determine the maximum possible flow through this path (the minimum residual capacity along the path).
4. Update Flows: Increase the flow along the path by the determined amount and update the residual capacities accordingly.
5. Repeat: Repeat steps 2-4 until no more augmenting paths can be found.

Implementation

Below is a Python implementation of the Edmonds-Karp algorithm using BFS to find augmenting paths:

from collections import deque

def bfs(capacity, flow, s, t):
    parent = {}
    visited = set()
    queue = deque([s])
    
    while queue:
        u = queue.popleft()
        if u == t:
            break
        
        for v in range(len(capacity)):
            residual_capacity = capacity[u][v] - flow[u][v]
            if v not in visited and residual_capacity > 0:
                parent[v] = (u, residual_capacity)
                visited.add(v)
                queue.append(v)
    
    path_flow = float('Inf')
    s = t
    while s != source:
        u, residual_capacity = parent[s]
        path_flow = min(path_flow, residual_capacity)
        s = u
    
    s = t
    while s != source:
        u, _ = parent[s]
        flow[u][s] += path_flow
        flow[s][u] -= path_flow
        s = u
    
    return path_flow

def edmonds_karp(capacity, source, sink):
    num_vertices = len(capacity)
    flow = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
    
    max_flow = 0
    while True:
        path_flow = bfs(capacity, flow, source, sink)
        if path_flow == 0:
            break
        max_flow += path_flow
    
    return max_flow

# Example usage
capacity = [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0]
]

source = 0
sink = 5
print("The maximum possible flow is", edmonds_karp(capacity, source, sink))

Explanation

1. BFS Function: The bfs function finds an augmenting path from the source to the sink using BFS. It returns the minimum residual capacity along this path.
2. Flow Augmentation: Once an augmenting path is found, the flow is augmented by the minimum residual capacity of the path.
3. Edmonds-Karp Function: The edmonds_karp function repeatedly calls the bfs function to find and augment paths until no more paths can be found.

Complexity Analysis

• Time Complexity: \( O(VE^2) \), where \( V \) is the number of vertices and \( E \) is the number of edges.
• Space Complexity: \( O(V^2) \) for storing the flow matrix.

The Edmonds-Karp algorithm has a polynomial time complexity, making it suitable for networks with moderate sizes. The use of BFS ensures that the running time is predictable and not dependent on the specific capacities or flows in the network.

Best Practices

1. Input Validation: Ensure that the input graph is valid and that the source and sink are distinct vertices.
2. Edge Cases: Consider edge cases such as networks with no edges, networks where the source and sink are directly connected, and networks with multiple paths between the source and sink.
3. Optimization: For large networks, consider optimizations such as using adjacency lists instead of matrices to reduce space complexity.

Conclusion

The Edmonds-Karp algorithm is a robust and efficient method for computing maximum flow in a network. Its predictable running time and simplicity make it a popular choice for educational purposes and practical applications. By understanding the underlying principles and implementation details, you can effectively apply this algorithm to solve complex network flow problems.