DSA Edmonds-Karp Algorithm

Welcome to TheCodingCollege.com! In this article, we delve into the Edmonds-Karp Algorithm, a specialized implementation of the Ford-Fulkerson method for solving Maximum Flow problems in a flow network. The algorithm is widely appreciated for its efficiency in terms of guaranteed polynomial time complexity.

What is the Edmonds-Karp Algorithm?

The Edmonds-Karp Algorithm is an enhanced version of the Ford-Fulkerson Algorithm, where the Breadth-First Search (BFS) is used to find the shortest augmenting path in terms of the number of edges. This modification ensures better performance compared to the generic Ford-Fulkerson method.

Key Features

  1. Finds the maximum flow in a directed graph with capacity constraints.
  2. Uses BFS to ensure shortest path selection.
  3. Has a time complexity of O(Vâ‹…E2), where V is the number of vertices and E is the number of edges.

Applications of Edmonds-Karp Algorithm

  1. Network Optimization: Optimizing data flow in telecommunication and internet networks.
  2. Bipartite Matching: Solving job assignment and pairing problems.
  3. Transportation Networks: Determining the maximum flow of goods or traffic.
  4. Resource Allocation: Efficiently allocating resources in production systems.

Steps of the Edmonds-Karp Algorithm

  1. Initialize Flows:
    • Set all flows in the network to 0.
  2. Find Augmenting Path Using BFS:
    • Use BFS to find the shortest path (in terms of edges) from the source (ss) to the sink (tt) in the residual graph.
  3. Calculate Path Flow:
    • Determine the minimum capacity along the augmenting path.
  4. Update Residual Graph:
    • Subtract the path flow from the forward edges.
    • Add the path flow to the backward edges.
  5. Repeat Until No Augmenting Path Exists:
    • Continue the process until BFS can no longer find an augmenting path.
  6. Output Maximum Flow:
    • The sum of flows along the edges originating from the source is the maximum flow.

Example of Edmonds-Karp Algorithm

Graph Representation

  • Vertices: s,a,b,c,t
  • Edges and Capacities:
    • s→ a: 10
    • s→ b: 5
    • a→ c: 15
    • b→ c: 10
    • c→ t: 10
    • a→ b: 4

Python Implementation of Edmonds-Karp Algorithm

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, u, v, capacity):
        self.graph[u][v] = capacity

    def bfs(self, source, sink, parent):
        visited = [False] * self.V
        queue = deque([source])
        visited[source] = True

        while queue:
            u = queue.popleft()
            for v, capacity in enumerate(self.graph[u]):
                if not visited[v] and capacity > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
                    if v == sink:
                        return True
        return False

    def edmonds_karp(self, source, sink):
        parent = [-1] * self.V
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float('Inf')
            s = sink

            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            max_flow += path_flow
            v = sink

            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

# Example Usage
g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(1, 3, 12)
g.add_edge(2, 4, 14)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source, sink = 0, 5
print("The Maximum Flow is:", g.edmonds_karp(source, sink))

Advantages

  1. Guaranteed Polynomial Time Complexity: The algorithm ensures O(Vâ‹…E2).
  2. Simplicity: Easy to implement using BFS.
  3. Deterministic: Produces the same result for the same input graph.

Disadvantages

  1. Inefficiency for Sparse Graphs: Can be slower than advanced algorithms for sparse graphs.
  2. Not Suitable for Real-Time Applications: Computational overhead may be high for large-scale networks.

Time Complexity

  • BFS Time Complexity: O(V+E).
  • Overall Complexity: O(Vâ‹…E2).

Real-World Applications

  1. Telecommunications: Ensuring efficient routing of data.
  2. Logistics: Managing traffic or transportation flow.
  3. Resource Scheduling: Optimizing job or task assignments.

Conclusion

The Edmonds-Karp Algorithm is a robust and reliable solution for solving maximum flow problems. By leveraging BFS, it guarantees efficiency and effectiveness, making it a cornerstone in the study of graph algorithms.

Leave a Comment