The Ford-Fulkerson algorithm is used to find the maximum flow in a flow network.

It is based
on the idea of finding augmenting paths in a residual graph and adding the flow along those
paths until no more augmenting paths can be found.

Example 1
Consider the following directed graph where s is the source and t is the sink. Each edge has a
capacity:

From To Capacity

S A 10

S B 5

A B 15

A T 10

B T 10

Goal

Find the maximum flow from S to T.

Step-by-Step Execution
Step 1: Initialize Flows
1. Initially, all flows are set to 0. The residual capacity for each edge is equal to its original
capacity.

Step 2: Augmenting Paths

An augmenting path in a flow network is a path from the source to the sink in the residual
graph where every edge has available capacity greater than zero.

In simpler terms, an augmenting path is a path along which we can still push more flow from
source to sink.

1
We repeatedly find augmenting paths from S to T in the residual graph, and augment the flow
along those paths.

Iteration 1
Find Augmenting Path: S→A→T
 Residual capacities:
o S→A:10

o A→T:10

Bottleneck (Minimum Residual Capacity): min(10,10) = 10

Update Flows and Residual Capacities:
 Flow along S→A: 0+10 = 10, residual capacity = 10−10 = 0.
 Flow along A→T: 0+10 = 10, residual capacity = 10−10 = 0.
Updated residual graph:

From To Residual Capacity

S A 0

S B 5

A B 15

A T 0

B T 10

Iteration 2
Find Augmenting Path: S→B→T
 Residual capacities:
o S→B:5

o B→T:10

Bottleneck (Minimum Residual Capacity): min(5,10) = 5

2
Update Flows and Residual Capacities:
 Flow along S→B: 0+5 = 5, residual capacity = 5−5 = 0.
 Flow along B→T: 0+5 = 5, residual capacity = 10−5 = 5.
Updated residual graph:

From To Residual Capacity

S A 0

S B 0

A B 15

A T 0

B T 5

Iteration 3
No more augmenting paths exist from S to T in the residual graph.

Step 3: Calculate Maximum Flow

The maximum flow is the total flow into the sink T, which is:
Max Flow = (flow from A→T)+(flow from B→T) = 10+5 = 15.

Final Result

 Maximum Flow: 15
 Flow Distribution:
o S→A:10, S→B:5.

o A→T:10, B→T:5.

This demonstrates the Ford-Fulkerson Algorithm in finding the maximum flow through a
network.

3
Python Code
import networkx as nx

def create_graph():
"""Create a directed graph with given capacities."""
G = nx.DiGraph()

# Adding edges with capacities

edges = [
('S', 'A', 10),
('S', 'B', 5),
('A', 'B', 15),
('A', 'T', 10),
('B', 'T', 10)
]

for u, v, capacity in edges:

G.add_edge(u, v, capacity=capacity)

return G

def ford_fulkerson_dfs(G, source, sink):

"""Implementation of the Ford-Fulkerson algorithm using DFS."""

def dfs_find_augmenting_path(G, source, sink, path, visited):

"""Perform DFS to find an augmenting path."""
if source == sink:
return path

visited.add(source)

for neighbor in G.neighbors(source):

capacity = G[source][neighbor]['capacity']
if neighbor not in visited and capacity > 0:
result = dfs_find_augmenting_path(G, neighbor, sink, path +
[(source, neighbor)], visited)
if result:
return result

return None

# Initialize max flow and residual graph

total_flow = 0
residual_graph = G.copy()

while True:
visited = set()
path = dfs_find_augmenting_path(residual_graph, source, sink, [],
visited)

if not path:
break # No more augmenting paths

# Find the bottleneck capacity

bottleneck = min(residual_graph[u][v]['capacity'] for u, v in path)

4
 # Update the residual graph
for u, v in path:
residual_graph[u][v]['capacity'] -= bottleneck # Reduce forward
edge capacity
if residual_graph.has_edge(v, u):
residual_graph[v][u]['capacity'] += bottleneck # Increase
reverse edge capacity
else:
residual_graph.add_edge(v, u, capacity=bottleneck) # Create
reverse edge if not exists

total_flow += bottleneck
print(f"Augmenting Path Found: {' → '.join([u for u, v in path])} →
{sink}, Flow Added: {bottleneck}")

print(f"\n Maximum Flow: {total_flow}")

return total_flow

# Create the graph

G = create_graph()

# Compute maximum flow from 'S' to 'T' using Ford-Fulkerson

max_flow = ford_fulkerson_dfs(G, 'S', 'T')

Explanation of the Code

1. Graph Creation (create_graph())

o Creates a directed graph with given capacities using NetworkX.
2. DFS-based Augmenting Path Search (dfs_find_augmenting_path())
o Uses Depth-First Search (DFS) to find an augmenting path in the residual graph.
3. Updating Residual Graph
o Subtracts the bottleneck capacity from the forward edges.
o Adds the bottleneck capacity to the reverse edges (to allow for flow correction if
needed).
4. Iterates Until No More Augmenting Paths Exist
o Keeps finding paths and updating flow until no more paths are available.

Expected Output
yaml
CopyEdit
Augmenting Path Found: S → A → T, Flow Added: 10
Augmenting Path Found: S → B → T, Flow Added: 5

Maximum Flow: 15

5
Example 2
Find the maximum flow from source S to sink T in the following flow network:

Graph Representation:

Nodes: S,A,B,C,D,T

Edges and capacities:

 S→A 10
 S→C 10
 A→B 4
 A→C 2
 A→D 8
 B→T 10
 C→D 9
 D→B 6
 D→T 10

In this example, S is the source, and T is the sink.

Initial flow = 0.

Choosing path S – A – D – T, with bottleneck 8 in A – D, yields the following results:

S – A: 8/10, residual flow: 2

A – D: 8/8, residual flow: 0

D – T: 8/10, residual flow: 2

Inflow at S is 8 and outflow at T is 8.

Additionally, the inflow and outflow at every node are equal.

Choosing path S – C – D – T, with bottleneck 2 in D – T, yields the following results:

S – C: 2/10, residual flow: 8

C – D: 2/9, residual flow: 7

D – T: 2/2, residual flow: 0

6
Inflow at S is 8 + 2 = 10 and outflow at T is also 8 + 2 = 10.

Additionally, the inflow and outflow at every node are equal.

Choosing path S – C – D – A – B – T (backward edge) with bottleneck 4 in B – T, yields the

following results:

S – C: 4/8, residual flow: 4

C – D: 4/7, residual flow: 3

D – A: -4/8, residual flow: 4

A – B: 4/4, residual flow: 0

B – T: 4/10, residual flow: 6

Inflow at S is 10 + 4 = 14 and outflow at T is also 10 + 4 = 14.

Additionally, the inflow and outflow at every node are equal.

Choosing path S – A – D – B – T with bottleneck 2 in S – A, yields the following results:

S – A: 2/2, residual flow: 0

A – D: 2/4, residual flow: 2

D – B: 2/6, residual flow: 4

B – T: 2/6, residual flow: 4

Inflow at S is 14 + 2 = 16 and outflow at T is also 14 + 2 = 16.

Additionally, the inflow and outflow at every node are equal.

Choosing path S – C – D – B – T with bottleneck 3 in C – D, yields the following results:

S – C: 3/4, residual flow: 1

C – D: 3/3, residual flow: 0

D – B: 3/4, residual flow: 1

7
B – T: 3/4, residual flow: 1

Inflow at S is 16 + 3 = 19 and outflow at T is also 16 + 3 = 19.

Additionally, the inflow and outflow at every node are equal.

Termination

1. No more augmenting paths are available.

2. Maximum flow: 19.

Final Result

The maximum flow from S to T is 19.

Python Code
python
CopyEdit
from collections import deque, defaultdict

def edmonds_karp(graph, source, sink):

# Create a residual graph and fill with given capacities
residual = defaultdict(lambda: defaultdict(int))
for u in graph:
for v, cap in graph[u].items():
residual[u][v] = cap
# Ensure the reverse edge exists in the residual graph
if v not in residual:
residual[v] = defaultdict(int)

max_flow = 0

while True:
# Find an augmenting path using BFS
parent = {} # To store the path: child -> parent
queue = deque([source])
parent[source] = None # source has no parent
while queue and sink not in parent:
u = queue.popleft()
for v in residual[u]:
# If there is available capacity and v is not visited
if residual[u][v] > 0 and v not in parent:
parent[v] = u
queue.append(v)
if v == sink:
break

8
 # If we didn't reach the sink, no more augmenting paths exist
if sink not in parent:
break

# Find the bottleneck capacity on the found path

v = sink
path_flow = float('inf')
while v != source:
u = parent[v]
path_flow = min(path_flow, residual[u][v])
v = u

# Update the residual capacities of the edges and reverse edges

v = sink
while v != source:
u = parent[v]
residual[u][v] -= path_flow
residual[v][u] += path_flow
v = u

max_flow += path_flow

return max_flow
# Define the graph with capacities
graph = {
'S': {'A': 10, 'C': 10},
'A': {'B': 4, 'C': 2, 'D': 8},
'B': {'T': 10},
'C': {'D': 9},
'D': {'B': 6, 'T': 10},
'T': {}
}

source = 'S'
sink = 'T'
max_flow = edmonds_karp(graph, source, sink)
print("The maximum flow from {} to {} is: {}".format(source, sink, max_flow))

Explanation

1. Residual Graph Setup:

We build a residual graph from the given graph. For every edge u→v with capacity, we
initialize the reverse edge v→u with capacity 0 (implicitly, using a defaultdict).
2. BFS for Augmenting Path:
We use a queue to perform a BFS starting from the source. The parent dictionary keeps
track of the path. Once the sink is reached, we stop the BFS.
3. Augmentation:
After finding an augmenting path, we determine the bottleneck (minimum capacity along
that path), then update the residual capacities for both the forward and reverse edges.
4. Termination:
The loop stops when no more augmenting paths from source to sink can be found.

9
Python Output
css
CopyEdit
The maximum flow from S to T is: 19

This confirms that the maximum flow in the network is 19.

Conclusion
The Ford-Fulkerson algorithm is a powerful technique for solving the maximum flow
problem in a flow network. The algorithm uses augmenting paths to iteratively increase the flow
until no more augmenting paths can be found.

10