DSA Ford-Fulkerson Algorithm

Welcome to TheCodingCollege.com! This article explores the Ford-Fulkerson Algorithm, a fundamental method used to solve the Maximum Flow problem in a flow network. This algorithm forms the backbone of many advanced graph-based solutions, making it an essential concept in Data Structures and Algorithms (DSA).

What is the Ford-Fulkerson Algorithm?

The Ford-Fulkerson Algorithm computes the maximum flow in a flow network. It operates by finding augmenting paths in the network and increasing the flow until no further improvements can be made.

Core Ideas

  1. Use an iterative process to find augmenting paths in the network.
  2. Update flows and residual capacities based on these paths.
  3. Terminate when no more augmenting paths exist.

Features of the Algorithm

  • Input: A directed graph with a source (ss) and sink (tt), where edges have capacities.
  • Output: The maximum possible flow from ss to tt.

Applications of Ford-Fulkerson Algorithm

  1. Network Optimization: Maximizing data flow in computer networks.
  2. Project Management: Resource allocation in supply chains.
  3. Bipartite Matching: Solving pairing problems like job assignments.
  4. Logistics: Optimizing flow in transportation networks.

Steps of the Ford-Fulkerson Algorithm

  1. Initialize:
    • Set all flows in the network to 0.
  2. Find Augmenting Path:
    • Use DFS or BFS to locate a path from ss to tt where the residual capacity of edges is greater than 0.
  3. Calculate Path Flow:
    • Determine the minimum residual capacity along the augmenting path.
  4. Update Flows:
    • Adjust flows along the path:
      • Reduce residual capacity of forward edges by the path flow.
      • Increase residual capacity of backward edges by the path flow.
  5. Repeat:
    • Continue finding augmenting paths until none exist.
  6. Output Maximum Flow:
    • The sum of all flows from the source to the sink.

Example of Ford-Fulkerson

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

Augmenting Path Process

  1. Start with s→a→c→t
    • Path flow = 10.
  2. Adjust residual capacities and repeat:
    • s→b→c→t.
    • Path flow = 55.

Maximum Flow = 1515.

Python Implementation of Ford-Fulkerson 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 ford_fulkerson(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.ford_fulkerson(source, sink))

Advantages

  1. Simple to implement with integer capacities.
  2. Provides an intuitive understanding of flow problems.

Disadvantages

  1. Inefficient for dense graphs.
  2. High time complexity for fractional capacities or large graphs.

Time Complexity

  • O(E×max_flow), where E is the number of edges.

Real-World Applications

  • Internet Traffic Management: Efficiently route data packets.
  • Resource Allocation: Assign resources optimally in a production environment.
  • Scheduling Problems: Balance workloads efficiently.

Conclusion

The Ford-Fulkerson Algorithm is a cornerstone of graph theory, enabling solutions to maximum flow problems with practical applications in various domains.

Leave a Comment