• $𝑠$: Source
• $𝐴$ & $𝐵$: Intermediate nodes
• $𝑡$: Sink

Capacities:

• $𝑠\to 𝑡$: 10
• $𝑠\to 𝐵$: 5
• $𝐴\to 𝐵$: 15
• $𝐴\to 𝑡$: 10
• $𝐵\to 𝑡$: 10

Step 1: Initialize flow to 0

All flows through the edges are initially set to 0.

Step 2: Find an augmenting path

Find an augmenting path using Depth-First Search (DFS). Start from the source $𝑠$

The minimum capacity along this path is 10 (bottleneck on edge $𝐴\to 𝑡$)

We can push a flow of 10 units along this path.

Step 3: Update the residual graph

• $𝑠\to 𝐴$: Capacity becomes $10-10=0$ (no residual capacity)
• $𝐴\to 𝑡$: Capacity becomes $10-10=0$ (no residual capacity)

Step 4: Find another augmenting path

Find another augmenting path.

We cannot use $𝑠\to 𝐴$ or $𝐴\to 𝑡$ because their capacities are 0.

The minimum capacity along this path is 5 (bottleneck on edge $𝑠\to 𝐵$)

We can push a flow of 5 units along this path

Step 5: Update the residual graph

• $𝑠\to 𝐵$: Capacity becomes $5-5=0$
• $𝐵\to 𝑡$: Capacity becomes $10-5=5$

Step 6: Termination

No more augmenting paths from $𝑠$ to $𝑡$ can be found, as all edges from $𝑠$ are fully saturated

Maximum flow:

• $𝑠\to 𝐴\to 𝑡$: 10 units
• $𝑠\to 𝐵\to 𝑡$: 5 units

Thus, the maximum flow from source $𝑠$ to sink $𝑡$ is 15 units

Step 7: Final Flow Distribution