Max Flow (Ford-Fulkerson, Edmonds-Karp) - CSU083 | Shoolini University

Max Flow (Ford-Fulkerson, Edmonds-Karp)

2025, February 7

1. Prerequisites

Before understanding the Max Flow algorithms, you need to be familiar with the following concepts:

1.1 Graph Theory

1.2 Flow Networks

1.3 BFS and DFS

2. What is Max Flow?

Max Flow is an algorithmic problem that determines the maximum possible flow from a source node to a sink node in a flow network while respecting edge capacities.

2.1 Ford-Fulkerson Algorithm

A method using DFS (or BFS) to repeatedly find augmenting paths and push flow until no further flow can be added.


def ford_fulkerson(graph, source, sink):
    max_flow = 0
    while augmenting_path_exists(graph, source, sink):
        path_flow = min_capacity_in_path(graph, source, sink)
        max_flow += path_flow
        update_residual_graph(graph, path_flow)
    return max_flow

2.2 Edmonds-Karp Algorithm

A specialization of Ford-Fulkerson that always uses BFS to find augmenting paths, ensuring polynomial time complexity.


from collections import deque

def bfs(graph, source, sink, parent):
    queue = deque([source])
    visited = set([source])
    while queue:
        node = queue.popleft()
        for neighbor, capacity in graph[node]:
            if neighbor not in visited and capacity > 0:
                parent[neighbor] = node
                if neighbor == sink:
                    return True
                queue.append(neighbor)
                visited.add(neighbor)
    return False

3. Why does this algorithm exist?

Max Flow algorithms are used to model and solve problems involving limited resources moving through a network:

4. When should you use it?

Use Max Flow when:

5. Comparison with Alternatives

5.1 Strengths

5.2 Weaknesses

5.3 Alternatives

6. Basic Implementation

Below is the basic implementation of the Max Flow algorithm using the Ford-Fulkerson method with BFS (Edmonds-Karp variation) in Python.


from collections import deque

class MaxFlow:
    def __init__(self, graph):
        self.graph = graph  # Residual graph
        self.n = len(graph)  # Number of nodes

    def bfs(self, source, sink, parent):
        """Perform BFS to find an augmenting path from source to sink."""
        visited = [False] * self.n
        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:  # Edge with available capacity
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
                    if v == sink:
                        return True
        return False

    def ford_fulkerson(self, source, sink):
        """Finds the maximum flow from source to sink."""
        parent = [-1] * self.n
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            v = sink

            # Find minimum residual capacity along the path
            while v != source:
                u = parent[v]
                path_flow = min(path_flow, self.graph[u][v])
                v = u

            # Update residual graph
            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow  # Reverse flow for residual graph
                v = u

            max_flow += path_flow

        return max_flow

# Example graph as adjacency matrix
graph = [
    [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]
]

maxflow = MaxFlow(graph)
source, sink = 0, 5
print("The maximum possible flow is:", maxflow.ford_fulkerson(source, sink))

7. Dry Run

Given the graph:

    (0) --16--> (1) --10--> (2)
      |          |          |
     13         12         14
      |          |          |
    (3) --9--> (4) --7--> (5)
           \      |      /
           20    4     4

7.1 Initial Residual Graph

Node Outgoing Edges (Capacity)
0 (1, 16), (2, 13)
1 (2, 10), (3, 12)
2 (1, 4), (4, 14)
3 (2, 9), (5, 20)
4 (3, 7), (5, 4)
5 -

7.2 Step-by-Step Execution

Iteration 1: BFS Finds Path 0 → 1 → 3 → 5
  • Path Flow = min(16, 12, 20) = 12
  • Update Residual Graph: Reduce forward capacities and increase reverse flows.
Iteration 2: BFS Finds Path 0 → 2 → 4 → 5
  • Path Flow = min(13, 14, 4) = 4
  • Update Residual Graph.
Iteration 3: BFS Finds Path 0 → 2 → 1 → 3 → 5
  • Path Flow = min(9, 4, 8) = 4
  • Update Residual Graph.

7.3 Final Flow

The total maximum flow from source (0) to sink (5) is 23.

8. Time & Space Complexity Analysis

8.1 Ford-Fulkerson (DFS-based) Complexity

Why \(O(E \cdot \max F)\) in the worst case?

8.2 Edmonds-Karp (BFS-based) Complexity

Why \(O(VE^2)\) in the worst case?

9. Space Complexity Analysis

9.1 Ford-Fulkerson Space Complexity

9.2 Edmonds-Karp Space Complexity

10. Trade-offs

10.1 Ford-Fulkerson vs. Edmonds-Karp

Algorithm Advantages Disadvantages
Ford-Fulkerson (DFS-based) Simple to implement, works well on small graphs. Unpredictable time complexity, may run indefinitely with irrational capacities.
Edmonds-Karp (BFS-based) Guaranteed polynomial time \(O(VE^2)\), finds shortest augmenting paths. Slower than more advanced methods like Dinic’s or Push-Relabel for large graphs.

10.2 When to Use Which Algorithm?

  • Ford-Fulkerson: When the graph is small or integer capacities are low.
  • Edmonds-Karp: When a reliable and predictable polynomial-time solution is required.
  • Push-Relabel (better than both for large graphs): \(O(V^3)\), often faster for dense graphs.
  • Dinic’s Algorithm: Best for large and dense graphs (\(O(V^2E)\)).

11. Optimizations & Variants

11.1 Common Optimizations

11.2 Variants of Max Flow Algorithms

12. Iterative vs. Recursive Implementations

12.1 Iterative Implementation (BFS/Queue-based)

Edmonds-Karp uses an iterative BFS approach to find the shortest augmenting path efficiently.


from collections import deque

def bfs(graph, source, sink, parent):
    queue = deque([source])
    visited = set([source])

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

12.2 Recursive Implementation (DFS-based Ford-Fulkerson)

The classic Ford-Fulkerson method can be implemented recursively using DFS.


def dfs(graph, u, sink, parent, flow):
    if u == sink:
        return flow

    for v, capacity in enumerate(graph[u]):
        if parent[v] == -1 and capacity > 0:
            new_flow = min(flow, capacity)
            parent[v] = u
            bottleneck = dfs(graph, v, sink, parent, new_flow)

            if bottleneck > 0:
                graph[u][v] -= bottleneck
                graph[v][u] += bottleneck
                return bottleneck
    return 0

12.3 When to Use Iterative vs. Recursive?

13. Edge Cases & Failure Handling

13.1 Common Pitfalls

13.2 Handling Failures

14. Test Cases to Verify Correctness

14.1 Basic Test Cases

Test Case 1: Simple Directed Graph

graph1 = [
    [0, 10, 10, 0, 0, 0],
    [0, 0, 5, 15, 0, 0],
    [0, 0, 0, 0, 10, 0],
    [0, 0, 0, 0, 10, 10],
    [0, 0, 0, 0, 0, 10],
    [0, 0, 0, 0, 0, 0]
]
assert max_flow(graph1, 0, 5) == 20
Test Case 2: Graph with Zero-Capacity Edges

graph2 = [
    [0, 0, 10, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 10, 0, 0],
    [0, 0, 0, 0, 10, 0],
    [0, 0, 0, 0, 0, 10],
    [0, 0, 0, 0, 0, 0]
]
assert max_flow(graph2, 0, 5) == 10
Test Case 3: Disconnected Graph

graph3 = [
    [0, 10, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],  # No outgoing edges from node 1
    [0, 0, 0, 10, 0, 0],
    [0, 0, 0, 0, 10, 0],
    [0, 0, 0, 0, 0, 10],
    [0, 0, 0, 0, 0, 0]
]
assert max_flow(graph3, 0, 5) == 0
Test Case 4: Graph with Cycles

graph4 = [
    [0, 10, 0, 10, 0, 0],
    [0, 0, 10, 0, 10, 0],
    [0, 0, 0, 10, 0, 10],
    [0, 0, 0, 0, 10, 10],
    [0, 0, 0, 0, 0, 10],
    [0, 0, 0, 0, 0, 0]
]
assert max_flow(graph4, 0, 5) == 20

15. Real-World Failure Scenarios

15.1 Network Congestion in Traffic Routing

Failure: Incorrect flow assignments can lead to bottlenecks, causing suboptimal routing.

Solution: Apply edge prioritization and adaptive pathfinding.

15.2 Load Balancing in Cloud Networks

Failure: Uneven flow distribution may overload certain servers.

Solution: Use weighted capacity-based scaling.

15.3 Water Distribution Networks

Failure: Pipes with lower capacities might be over-utilized.

Solution: Use push-relabel or capacity scaling to optimize flow.

15.4 Electrical Grid Overload

Failure: Sudden high demand might cause network-wide failures.

Solution: Implement real-time monitoring with flow updates.

16. Real-World Applications & Industry Use Cases

16.1 Network Flow Optimization

Used in computer networks for efficient bandwidth allocation and congestion control.

16.2 Transportation & Logistics

Max Flow helps optimize transport routes and supply chains.

16.3 Water & Electricity Distribution

Used to model pipelines and power grids.

16.4 Bipartite Matching & Workforce Allocation

Used in job assignments and resource allocation.

16.5 Image Segmentation & AI

Max Flow is used in computer vision and machine learning.

17. Open-Source Implementations

17.1 NetworkX (Python Library)

NetworkX provides built-in functions for computing max flow:


import networkx as nx

G = nx.DiGraph()
G.add_edge('S', 'A', capacity=10)
G.add_edge('S', 'B', capacity=5)
G.add_edge('A', 'B', capacity=15)
G.add_edge('A', 'T', capacity=10)
G.add_edge('B', 'T', capacity=10)

max_flow = nx.maximum_flow(G, 'S', 'T')
print("Max Flow:", max_flow[0])

17.2 Boost Graph Library (C++ Standard Library)

Provides efficient max-flow implementations for high-performance applications.

17.3 LEDA & Google OR-Tools

Industry-level libraries for logistics, supply chain, and AI.

18. Practical Project: Traffic Flow Optimization

18.1 Problem Statement

Use Max Flow to optimize city traffic between key intersections.

18.2 Implementation


import networkx as nx
import matplotlib.pyplot as plt

# Define a directed graph
G = nx.DiGraph()
edges = [
    ("A", "B", 10), ("A", "C", 15), ("B", "D", 10),
    ("C", "D", 10), ("C", "E", 10), ("D", "T", 15),
    ("E", "T", 10)
]
for u, v, capacity in edges:
    G.add_edge(u, v, capacity=capacity)

# Compute Max Flow
source, sink = "A", "T"
max_flow, flow_dict = nx.maximum_flow(G, source, sink)

print(f"Maximum Traffic Flow: {max_flow}")
print("Flow Distribution:", flow_dict)

# Visualization
pos = nx.spring_layout(G)
edge_labels = {(u, v): G[u][v]['capacity'] for u, v in G.edges()}
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()

18.3 Expected Output

18.4 Real-World Impact

19. Competitive Programming & System Design Integration

19.1 Max Flow in Competitive Programming

Max Flow algorithms are frequently used in competitive programming problems involving graph-based optimizations. Some common problem types include:

19.2 Max Flow in System Design

In real-world systems, Max Flow is used for large-scale optimizations:

20. Assignments

20.1 Solve at Least 10 Problems

Practice solving these problems using Max Flow:

  1. FASTFLOW - Fast Maximum Flow
  2. MBIPART - Maximum Bipartite Matching
  3. DRUNK - Drunk (Flow + Shortest Path)
  4. Codeforces 653D - Traffic Jams in the Land
  5. Codeforces 813E - Army Creation
  6. CSES 1694 - Download Speed
  7. CSES 1696 - Maximum Bipartite Matching
  8. UCV2013H - Maximum Network Flow
  9. LA3907 - Tokyo Traffic
  10. RAIL - Railroad

20.2 Implement Max Flow in a System Design Problem

Design a traffic management system using Max Flow:

20.3 Practice Under Time Constraints

Set a timer and solve Max Flow problems within:

Benchmark your performance and optimize your implementation!