• : Source
• & : Intermediate nodes
• : Sink

Capacities:

• : 10
• : 5
• : 15
• : 10
• : 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 )

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

Step 3: Update the residual graph

• : Capacity becomes (no residual capacity)
• : Capacity becomes (no residual capacity)

Step 4: Find another augmenting path

Find another augmenting path.

We cannot use or because their capacities are 0.

The minimum capacity along this path is 5 (bottleneck on edge )

We can push a flow of 5 units along this path

Step 5: Update the residual graph

• : Capacity becomes
• : Capacity becomes

Step 6: Termination

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

Maximum flow:

• : 10 units
• : 5 units

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

Step 7: Final Flow Distribution