Date: January 27, 2026

Topic: Ford-Fulkerson Algorithm

<aside> 📌 SUMMARY:

In a max-flow problem, we want to find the greatest amount of flow that can be sent from the source to the sink while respecting edge capacities and flow conservation. This is useful in settings like supply networks, transportation, and network traffic. If the graph has anti-parallel edges, we may first transform it into an equivalent flow network, for example by introducing an auxiliary vertex so the standard formulation is easier to apply.

During Ford–Fulkerson, we work on the residual graph:

Recall

We want to maximize the amount of supply sent from $s$ to $t$

Notes

Max Flow Problem

image.png


Take note of the 2 constraints where:

Problem Formulation

Input

Goal

Constraints


It is possible for a max-flow problem to have multiple different flow assignments, depending on how flow is routed through the edges, while still having the same maximum flow value.

To verify that we have reached the maximum flow, we show that some bottleneck capacity bounds the flow from above, and that our flow achieves this bound.

In this example (right), the bottleneck is the total capacity of the edges entering the sink $t$, which is $5+7=12$. Since the flow into $t$ is $12$, the max flow has been achieved.

Max Flow Example

Given the weights of the graph, find a possible maximum flow

Given the weights of the graph, find a possible maximum flow

Specify a valid integer flow value for each edge in the graph to maximize the total flow out of $s$ and into $t$.

Each flow value must be non-negative and must not exceed the capacity of the respective edge.

Please enter a comma separated list for $sa, sb, sc, ad, ae, be, cf, dc, dt, ed, fe, ft$ (in this order)

$sa$ $sb$ $sc$ $ad$ $ae$ $be$ $cf$ $dc$ $dt$ $ed$ $fe$ $ft$
6 1 5 6 0 1 7 2 5 1 0 7
6 1 5 5 1 1 7 2 5 2 0 7
6 1 5 6 0 1 8 3 5 2 1 7

Explanation

Flow is represented by the green numbers, while the weights are represented by the red numbers

Flow is represented by the green numbers, while the weights are represented by the red numbers


Problem is well-defined regardless if we have a cycle or not.

Validity of Cycles

image.png


Remove anti-parallel edges by introducing an auxiliary vertex in the parallel edge, then copy over the weights for the edge that has the vertex added.

This allows us to remove the anti-parallel edge and use max-flow.