Network Flow · study.

Imagine a network of pipes carrying water from a source to a sink, each pipe with a maximum capacity. How much water can you push through end to end? This is the maximum flow problem, and its reach extends far past plumbing: routing traffic, scheduling jobs, matching applicants to jobs, even segmenting images all reduce to it. Max-flow is one of algorithm design's great modeling tools; the art, as Erickson stresses, lies in recognizing a flow problem.¹

Flow networks

Think of routing a single commodity (water, electricity, traffic, money) from a source $s$ to a sink $t$ across a network whose edges have limited throughput.

A flow is a function $f : E \to R$ on the edges. The single most useful piece of bookkeeping is the net flow out of a vertex $v$ , written using the boundary symbol $\partial$ :

\partial f (v) := w : (v, w) \in E \sum f (v, w) - u : (u, v) \in E \sum f (u, v) = (flow out of v) - (flow into v) .

A flow is feasible when it obeys two rules:

Non-negativity & capacity. $0 \leq f (u, v) \leq c (u, v)$ for every edge: no edge runs backward, and none carries more than its capacity.
Conservation. $\partial f (v) = 0$ for every vertex $v \in / {s, t}$ : nothing is created or destroyed at an interior node. (When conservation holds at every vertex, $f$ is a circulation.)

The value of an $s$ – $t$ flow is the net amount leaving the source, $∣ f ∣ := \partial f (s)$ . A short computation shows this is the same as the net amount arriving at the sink: summing $\partial f (v)$ over all vertices counts each edge's flow once with a $+$ and once with a $-$ , so $\sum_{v \in V} \partial f (v) = 0$ ; conservation kills every interior term, leaving $\partial f (s) + \partial f (t) = 0$ , i.e. $∣ f ∣ = \partial f (s) = - \partial f (t)$ . The maximum-flow problem is to find a feasible flow of greatest value.

Below is a worked network; each edge is labeled $f / c$ (flow over capacity), realizing $∣ f ∣ = 12$ units pushed from $s$ to $t$ :

A flow network with edges labeled flow over capacity, carrying a flow of value 12 from

s

t

Conservation is the statement that each interior node balances. Take vertex $b$ : its incident flows are the outgoing $f_{ba} = 0$ , $f_{b d} = 2$ , $f_{b g} = 0$ and the incoming $f_{s b} = 2$ , so

\partial f (b) = f_{ba} + f_{b d} + f_{b g} - f_{s b} = 0 + 2 + 0 - 2 = 0.

The same check at $g$ reads $f_{g h} - (f_{s g} + f_{b g}) = 10 - (10 + 0) = 0$ , and at the source $\partial f (s) = f_{s b} + f_{s g} - f_{a s} = 2 + 10 - 0 = 12 = ∣ f ∣$ . Checking $\partial f (v) = 0$ at every interior vertex this way is how you verify a flow is feasible.

flow_network.pypython

from __future__ import annotations

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar

Label = TypeVar("Label", bound=Hashable)

class FlowEdge(Generic[Label]):
  """
    A directed edge of a flow network: capacity, current flow, and a link\n
    to its `residual` partner (the reverse edge sharing the same flow).\n
    The residual capacity — how much more can be pushed along this edge —\n
    is `capacity - flow`; pushing `amount` here pulls the same amount off\n
    the partner, so cancelling earlier flow is just a push on the reverse.\n
  """

  def __init__(
    self,
    source: FlowVertex[Label],
    target: FlowVertex[Label],
    capacity: float,
  ) -> None:
    self.source: FlowVertex[Label] = source
    self.target: FlowVertex[Label] = target
    self.capacity: float = capacity
    self.flow: float = 0.0
    self.residual: FlowEdge[Label] = self  # patched in by add_edge.

  def residual_capacity(self) -> float:
    """
      The spare room on this edge: how much more flow it can carry.\n
    """
    return self.capacity - self.flow

  def push(self, amount: float) -> None:
    """
      Send `amount` more along this edge, cancelling the same amount on\n
      the partner so the pair stays a consistent forward/backward view.\n
    """
    self.flow += amount
    self.residual.flow -= amount

  def __repr__(self) -> str:
    return (
      f"FlowEdge({self.source.label!r} -> {self.target.label!r}, "
      f"flow={self.flow}/{self.capacity})"
    )

class FlowVertex(Generic[Label]):
  """
    A flow-network vertex: a label plus the list of edges leaving it,\n
    including the synthetic reverse edges that make up the residual graph.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[FlowEdge[Label]] = []

  def __repr__(self) -> str:
    return f"FlowVertex({self.label!r})"

class FlowNetwork(Generic[Label]):
  """
    A directed flow network of FlowVertex objects linked by FlowEdge pairs.\n
    Every `add_edge` inserts both a forward edge (the real capacity) and a\n
    zero-capacity reverse edge; together they form the residual graph that\n
    augmenting-path algorithms search. Reading residual capacities and\n
    pushing flow are then uniform over forward and backward edges alike.\n
  """

  def __init__(self) -> None:
    self._vertices: dict[Label, FlowVertex[Label]] = {}

  def add_vertex(self, label: Label) -> FlowVertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    vertex: Optional[FlowVertex[Label]] = self._vertices.get(label)
    if vertex is None:
      vertex = FlowVertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    capacity: float,
  ) -> FlowEdge[Label]:
    """
      Add a forward edge of the given `capacity` and its zero-capacity\n
      reverse partner, wiring the two together as residuals. Returns the\n
      forward edge so callers (e.g. matching) can read its flow later.\n
    """
    source: FlowVertex[Label] = self.add_vertex(source_label)
    target: FlowVertex[Label] = self.add_vertex(target_label)

    # forward carries the real capacity; backward starts empty for cancellation.
    forward: FlowEdge[Label] = FlowEdge(source, target, capacity)
    backward: FlowEdge[Label] = FlowEdge(target, source, 0.0)
    forward.residual = backward
    backward.residual = forward

    source.outgoing.append(forward)
    target.outgoing.append(backward)
    return forward

  def vertex(self, label: Label) -> FlowVertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[FlowVertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  def edges(self) -> Iterator[FlowEdge[Label]]:
    """
      Each real (positive-capacity) forward edge once; reverse partners\n
      and any zero-capacity edges are skipped.\n
    """
    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        if edge.capacity > 0:
          yield edge

  def value(self, source_label: Label) -> float:
    """
      The value of the current flow: the net flow leaving the source.\n
    """
    source: FlowVertex[Label] = self._vertices[source_label]
    return sum(edge.flow for edge in source.outgoing if edge.capacity > 0)

  def reset_flow(self) -> None:
    """
      Zero every edge's flow, restoring the empty feasible flow.\n
    """
    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        edge.flow = 0.0

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[FlowVertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

Augmenting paths and the residual graph

How do we increase a flow? Find a path from $s$ to $t$ that still has spare room and push more along it. The bookkeeping device that makes this precise, and makes the algorithm correct, is the residual graph.

Concretely, each original edge $(u, v)$ splits into three cases on its residual capacity $c^{f}$ :

If $f_{uv} = 0$ (empty), put $(u, v) \in E_{f}$ with $c_{uv}^{f} = c_{uv}$ .
If $0 < f_{uv} < c_{uv}$ (partly used), put both: $(u, v)$ with $c_{uv}^{f} = c_{uv} - f_{uv}$ , and $(v, u)$ with $c_{v u}^{f} = f_{uv}$ .
If $f_{uv} = c_{uv}$ (saturated), put only the reverse $(v, u)$ with $c_{v u}^{f} = f_{uv}$ .

(We assume $G$ has no anti-parallel edges, at most one of $(u, v)$ , $(v, u)$ is in $E$ , so these reverse edges are unambiguous. Any graph can be preprocessed to satisfy this by splitting an edge through a dummy vertex.)

The backward edges are the subtle part that matters: pushing flow along $(v, u)$ cancels existing flow on $(u, v)$ , letting the algorithm undo earlier, suboptimal decisions. That is why a greedy fill paths until stuck approach can get stuck below optimum, while augmenting paths cannot. Below, the feasible flow from the worked network (top, with vertex $a$ omitted since all of its edges are empty) and the residual graph $G_{f}$ it induces (bottom); each residual edge is labeled with its capacity $c_{e}^{f}$ :

A feasible flow (top) and the residual graph it induces (bottom), with residual capacities labeled. Saturated edges (

s \to g

g \to h

) survive only as reverse edges; empty edges (

b \to g

) only as forward edges.

A single augmentation is easy to picture on a small network. Each edge below is labeled $f / c$ ; the highlighted residual path $s \to a \to b \to t$ has residual capacities $⟨ 1, 2, 3 ⟩$ , so its bottleneck is $1$ . Pushing one unit along it saturates $s \to a$ and lifts the flow value from $5$ to $6$ , with every interior vertex still balanced:

One augmentation: the residual path

s \to a \to b \to t

has capacities

⟨ 1, 2, 3 ⟩

, so its bottleneck is

1

; pushing

1

raises the flow value from

5

6

Why the back edges matter

It is tempting to skip the reverse edges entirely: repeatedly find an $s$ – $t$ path with spare forward capacity, saturate it, and stop when none remains. This greedy scheme is wrong, and the smallest counterexample shows why. Take the diamond below, every edge of capacity $1$ ; its maximum flow is $2$ (route $s \to u \to t$ and $s \to v \to t$ ). Suppose greedy first picks the zigzag path $s \to u \to v \to t$ and pushes $1$ along it. Now every remaining forward option is blocked: $s \to v$ has spare room but $v \to t$ is saturated, and $u \to t$ has spare room but $s \to u$ is saturated. Greedy halts at value $1$ , half the optimum.

The residual graph repairs exactly this. Because $u \to v$ carries flow $1$ , $G_{f}$ contains the reverse edge $(v, u)$ with capacity $1$ , and the path $s \to v \to u \to t$ becomes available. Pushing $1$ along it cancels the unit on $u \to v$ (its flow drops back to $0$ ), rerouting the first unit through $u \to t$ while the new unit takes $v \to t$ . No water flows backward; the algorithm has merely revised an earlier routing decision:

Greedy without back edges gets stuck. Top: saturating the zigzag

s \to u \to v \to t

blocks every remaining forward path at value

1

. Middle: the residual graph contains the reverse edge

(v, u)

, opening the path

s \to v \to u \to t

. Bottom: pushing

1

along it cancels the flow on

u \to v

and reaches the maximum value

2

The augmentation lemma

Before trusting the algorithm we must prove that augmenting actually produces a better feasible flow. Augmenting $f$ along a path $P$ by amount $k$ produces a new function $f^{'}$ defined edge-by-edge:

f_{uv}^{'} = ⎩ ⎨ ⎧ f_{uv} + k, f_{uv} - k, f_{uv}, if (u, v) on P, if (v, u) on P, otherwise (neither (u, v) nor (v, u) on P).

Proof. Four short claims, each just unfolding the definitions.

Non-negativity ( $f_{uv}^{'} \geq 0$ ). The only danger is a decrease, $f_{uv}^{'} = f_{uv} - k$ , which happens when the reverse $(v, u)$ lies on $P$ . But then $(v, u) \in E_{f}$ forces $c_{v u}^{f} = f_{uv}$ , and $k \leq c_{v u}^{f} = f_{uv}$ , so $f_{uv}^{'} = f_{uv} - k \geq 0$ .
Capacity ( $f_{uv}^{'} \leq c_{uv}$ ). The only danger is an increase, $f_{uv}^{'} = f_{uv} + k$ , which happens when $(u, v)$ lies on $P$ . Then $(u, v) \in E_{f}$ forces $c_{uv}^{f} = c_{uv} - f_{uv}$ , and $k \leq c_{uv}^{f}$ , so $f_{uv}^{'} = f_{uv} + k \leq f_{uv} + (c_{uv} - f_{uv}) = c_{uv}$ .
Conservation ( $\partial f^{'} (v) = 0$ for $v \in / {s, t}$ ). If $v \in / P$ , none of its incident terms change. If $v$ is an interior vertex of $P$ , the path enters $v$ once and leaves once; that pair of edges shifts the in- and out-flow by the same $k$ (with matching signs whether the path step is a forward or reverse edge), so $\partial f^{'} (v) = \partial f (v) = 0$ .
Value ( $∣ f^{'} ∣ = ∣ f ∣ + k$ ). $P$ uses exactly one edge out of $s$ and none into $s$ . That single edge gains $k$ (forward) or loses $- k$ across a reverse step, so $\partial f^{'} (s) = \partial f (s) + k$ , i.e. $∣ f^{'} ∣ = ∣ f ∣ + k$ . $□$

So every augmentation strictly increases the value while keeping $f$ legal. The converse, which the min-cut proof will need, also holds: if $f$ is not maximum, $G_{f}$ must contain an augmenting path. Putting the two together gives the equivalence at the center of the theory

\exists s - t path in G_{f} \leftrightarrow ∣ f ∣ is not maximum.

Ford-Fulkerson and Edmonds-Karp

The $Ford-Fulkerson$ method is then simple: while an augmenting path exists, push flow along it.²

Algorithm 1:

\textsc{Ford-Fulkerson}(G, s, t)

— augment until no path remains

1
foreach edge $(u, v) \in E$ do
2
$f(u, v) \gets 0$
3
while there exists an augmenting path $p$ from $s$ to $t$ in $G_f$ do
4
$c_f(p) \gets \min\set{c_f(u, v) : (u, v) \text{ on } p}$
bottleneck
5
foreach edge $(u, v)$ on $p$ do
6
$f(u, v) \gets f(u, v) + c_f(p)$
push forward
7
$f(v, u) \gets f(v, u) - c_f(p)$
cancel on reverse edge
8
return $f$

Running time rests on an invariant: if every capacity is an integer, $c : E \to N$ , then all residual capacities $c_{e}^{f}$ and flow values $f_{uv}$ stay integers throughout. Each augmentation then raises $∣ f ∣$ by at least $1$ , so there are at most $∣ f^{*} ∣$ iterations, each costing $O (m)$ to find a path and push along it (here $m = ∣ E ∣$ , $n = ∣ V ∣$ ):

T (m, n) \leq (# iters) \cdot O (m) \leq ∣ f^{*} ∣ \cdot O (m) = O (m ∣ f^{*} ∣) .

If additionally every capacity lies in $[1, C]$ , then $∣ f^{*} ∣ \leq \sum_{e} c_{e} \leq C m$ , giving $T (m, n, C) = O (m^{2} C)$ . This is pseudo-polynomial: fine for small capacities, but very slow when they are huge. The classic bad case has a middle edge of capacity $1$ between two paths of capacity $1000$ ; a naïve solver alternately pushes one unit forward and one unit back, taking $Ω (C)$ augmentations. (On irrational capacities the method may not even terminate.)

The Ford-Fulkerson bad case: a unit middle edge between two capacity-

1000

paths. A poor path choice alternately pushes one unit forward and back, taking

Ω (C)

augmentations.

The fix, due to $Edmonds-Karp$ , is to always pick the shortest augmenting path (fewest edges): find it with BFS in the residual graph.

Algorithm 2:

\textsc{Edmonds-Karp}(G, s, t)

— Ford-Fulkerson with BFS path choice

1
foreach edge $(u, v) \in E$ do
2
$f(u, v) \gets 0$
3
while BFS finds a shortest path $p$ from $s$ to $t$ in $G_f$ do
4
augment $f$ along $p$ by its bottleneck $c_f(p)$
5
return $f$

Why should the shortest path be any better? The analysis rests on a monotonicity property of BFS levels in the residual graph. Write $δ_{f} (v)$ for the number of edges on a shortest $s \to v$ path in $G_{f}$ .

Counting iterations now follows from a charging argument on critical edges. In each augmentation, at least one residual edge $(u, v)$ on the path has $c_{uv}^{f}$ equal to the bottleneck; that edge is critical and disappears from $G_{f}$ . For $(u, v)$ to become critical again, the reverse $(v, u)$ must first appear on some later shortest path, which requires $δ_{f} (v) = δ_{f} (u) + 1$ at the first event and $δ_{f^{'}} (u) = δ_{f^{'}} (v) + 1$ at the second. With the monotone lemma,

δ_{f^{'}} (u) = δ_{f^{'}} (v) + 1 \geq δ_{f} (v) + 1 = δ_{f} (u) + 2,

so $u$ 's level rises by at least $2$ between consecutive criticalities of $(u, v)$ . Levels live in ${0, 1, \dots, n - 1}$ (once $δ_{f} (u) > n - 1$ the vertex is unreachable and the edge never reappears on a path), so each of the at most $2 m$ residual edges is critical $O (n)$ times, giving $O (mn)$ augmentations in total. Each iteration is one BFS plus one path update, $O (m)$ work, for a strongly polynomial bound independent of capacities:

T (m, n) = O (mn) iterations \times O (m) per iteration = O (m^{2} n) = O (V E^{2}) .

For dense graphs this is far from the last word — Orlin's 2012 algorithm runs in $O (mn)$ , and you may cite max-flow as an $O (mn)$ black box — but $Edmonds-Karp$ is the version to know: two ideas (residual graph, BFS) and a clean proof.

ford_fulkerson.pypython

from collections.abc import Hashable
from typing import Optional, TypeVar

from flow_network import FlowEdge, FlowNetwork, FlowVertex

Label = TypeVar("Label", bound=Hashable)

def _find_augmenting_path(
  network: FlowNetwork[Label],
  source: FlowVertex[Label],
  sink: FlowVertex[Label],
) -> Optional[list[FlowEdge[Label]]]:
  """
    A source-to-sink path through edges with spare residual capacity,\n
    returned as its list of edges, or None if the sink is unreachable.\n
    Found by depth-first search over the residual graph.\n
  """
  visited: set[Label] = {source.label}
  path: list[FlowEdge[Label]] = []

  def explore(current: FlowVertex[Label]) -> bool:
    if current is sink:
      return True

    # try each unvisited neighbor with spare capacity, backtracking on dead ends.
    for edge in current.outgoing:
      neighbor: FlowVertex[Label] = edge.target
      if edge.residual_capacity() <= 0 or neighbor.label in visited:
        continue

      visited.add(neighbor.label)
      path.append(edge)
      if explore(neighbor):
        return True
      path.pop()

    return False

  return path if explore(source) else None

def ford_fulkerson(
  network: FlowNetwork[Label],
  source_label: Label,
  sink_label: Label,
) -> float:
  """
    The value of a maximum flow from `source_label` to `sink_label`.\n
    Mutates the network's edge flows in place to realize that flow, so\n
    the saturating assignment can be read off afterward (e.g. for min-cut\n
    or matching). Starts from the current flow; reset it first for a clean\n
    run.\n
  """
  # get-or-create: a terminal with no incident edge is a valid isolated
  # vertex carrying zero flow, not a missing key.
  source: FlowVertex[Label] = network.add_vertex(source_label)
  sink: FlowVertex[Label] = network.add_vertex(sink_label)
  max_flow: float = 0.0

  while True:
    path: Optional[list[FlowEdge[Label]]] = _find_augmenting_path(
      network, source, sink
    )
    if path is None:
      break

    # bottleneck: the least spare capacity along the path.
    bottleneck: float = min(edge.residual_capacity() for edge in path)
    for edge in path:
      edge.push(bottleneck)
    max_flow += bottleneck

  return max_flow

edmonds_karp.pypython

from collections import deque
from collections.abc import Hashable
from typing import Optional, TypeVar

from flow_network import FlowEdge, FlowNetwork, FlowVertex

Label = TypeVar("Label", bound=Hashable)

def _shortest_augmenting_path(
  network: FlowNetwork[Label],
  source: FlowVertex[Label],
  sink: FlowVertex[Label],
) -> Optional[list[FlowEdge[Label]]]:
  """
    A source-to-sink path with the fewest residual edges, returned as its\n
    list of edges, or None if the sink is unreachable. Found by BFS, so the\n
    first time the sink is reached the path to it is shortest.\n
  """
  came_from: dict[Label, FlowEdge[Label]] = {}
  visited: set[Label] = {source.label}
  queue: deque[FlowVertex[Label]] = deque([source])

  # bfs from the source; record the edge each vertex was first reached by.
  while queue:
    current: FlowVertex[Label] = queue.popleft()
    if current is sink:
      break

    for edge in current.outgoing:
      neighbor: FlowVertex[Label] = edge.target
      if edge.residual_capacity() > 0 and neighbor.label not in visited:
        visited.add(neighbor.label)
        came_from[neighbor.label] = edge
        queue.append(neighbor)

  if sink.label not in came_from:
    return None

  # walk the predecessor edges back from the sink, then reverse.
  path: list[FlowEdge[Label]] = []
  cursor: Label = sink.label
  while cursor != source.label:
    edge = came_from[cursor]
    path.append(edge)
    cursor = edge.source.label
  path.reverse()
  return path

def edmonds_karp(
  network: FlowNetwork[Label],
  source_label: Label,
  sink_label: Label,
) -> float:
  """
    The value of a maximum flow from `source_label` to `sink_label`,\n
    augmenting along BFS-shortest residual paths. Mutates the network's\n
    edge flows in place. Starts from the current flow; reset it first for\n
    a clean run.\n
  """
  # get-or-create: a terminal with no incident edge is a valid isolated
  # vertex carrying zero flow, not a missing key.
  source: FlowVertex[Label] = network.add_vertex(source_label)
  sink: FlowVertex[Label] = network.add_vertex(sink_label)
  max_flow: float = 0.0

  while True:
    path: Optional[list[FlowEdge[Label]]] = _shortest_augmenting_path(
      network, source, sink
    )
    if path is None:
      break

    bottleneck: float = min(edge.residual_capacity() for edge in path)
    for edge in path:
      edge.push(bottleneck)
    max_flow += bottleneck

  return max_flow

A complete run of Edmonds-Karp

Here is one full run, end to end. The network below has six vertices and seven edges (capacities on the edges); we run $Edmonds-Karp$ from the zero flow, scanning neighbors in alphabetical order so the BFS choices are reproducible. Each round we show the residual graph, the shortest augmenting path BFS finds (highlighted), and the bottleneck it pushes.

Round 1. With $f = 0$ the residual graph is $G$ : every edge appears forward at full capacity. BFS layers the vertices $s ∣ a, c ∣ b, d ∣ t$ and returns the length- $3$ path $s \to a \to b \to t$ . Its residual capacities are $⟨ 8, 5, 6 ⟩$ , so the bottleneck is $min (8, 5, 6) = 5$ : push $5$ , and the value rises $0 \to 5$ .

Round 2. Edge $a \to b$ is now saturated and survives only as the reverse edge $(b, a)$ ; $s \to a$ keeps forward capacity $8 - 5 = 3$ plus a reverse edge of capacity $5$ . BFS finds $s \to a \to d \to t$ with residual capacities $⟨ 3, 3, 8 ⟩$ ; the bottleneck is $3$ . Push $3$ : the value rises $5 \to 8$ , and both $s \to a$ and $a \to d$ saturate.

Rounds 1 and 2. Top: the initial residual graph (equal to

G

) with the first BFS path

s \to a \to b \to t

highlighted; its bottleneck is

min (8, 5, 6) = 5

. Bottom: the residual graph after pushing 5, with the second path

s \to a \to d \to t

highlighted; its bottleneck is

min (3, 3, 8) = 3

Round 3. The source's only remaining forward edge is $s \to c$ . BFS finds $s \to c \to d \to t$ with residual capacities $⟨ 6, 7, 5 ⟩$ (edge $d \to t$ has $8 - 3 = 5$ left); the bottleneck is $5$ . Push $5$ : the value rises $8 \to 13$ , and $d \to t$ saturates.

Round 4 (halt). BFS from $s$ now reaches $c$ (forward capacity $1$ remains on $s \to c$ ), then $d$ (via $c \to d$ , capacity $2$ ), then $a$ (via the reverse edge $(d, a)$ ) — and stops. Every edge out of this set is saturated, so $t$ is unreachable and the algorithm halts with $∣ f^{*} ∣ = 13$ .

Rounds 3 and 4. Top: the residual graph after round 2, with the third path

s \to c \to d \to t

highlighted; its bottleneck is

min (6, 7, 5) = 5

. Bottom: the final residual graph. The shaded vertices

{s, a, c, d}

are exactly those reachable from

s

;

t

is not among them, so no augmenting path remains.

The whole run in one table:

Round	Augmenting path	Residual capacities	Bottleneck	Value
1	$s \to a \to b \to t$	$⟨ 8, 5, 6 ⟩$	$5$	$0 \to 5$
2	$s \to a \to d \to t$	$⟨ 3, 3, 8 ⟩$	$3$	$5 \to 8$
3	$s \to c \to d \to t$	$⟨ 6, 7, 5 ⟩$	$5$	$8 \to 13$
4	none — $t$ unreachable	—	—	$13$

The final flow, edge by edge: $f_{s a} = 8$ , $f_{sc} = 5$ , $f_{ab} = 5$ , $f_{a d} = 3$ , $f_{c d} = 5$ , $f_{b t} = 5$ , $f_{d t} = 8$ . Every interior vertex balances ( $a$ : in $8$ , out $5 + 3$ ; $c$ : in $5$ , out $5$ ; $b$ : in $5$ , out $5$ ; $d$ : in $3 + 5$ , out $8$ ), and $∣ f^{*} ∣ = 8 + 5 = 13$ . Is $13$ really the maximum? The halting condition says yes, but the certificate that proves it is a cut — the subject of the next lesson, where this same network returns.

This continues in Max-Flow Min-Cut and Applications. There we prove why the halting flow is optimal — the max-flow min-cut theorem — and apply the abstraction to bipartite matching and a catalog of modeling reductions.

Erickson, Ch. 10 & 11 — Maximum Flows and Applications — the art of recognizing a problem as a flow problem. ↩
CLRS, Ch. 26 — Maximum Flow — the Ford-Fulkerson method augmenting along residual paths. ↩
CLRS, Ch. 26 — Maximum Flow — the Edmonds-Karp analysis via monotone shortest-path distances in the residual graph. ↩

Flow networks

Augmenting paths and the residual graph

Why the back edges matter

The augmentation lemma

Ford-Fulkerson and Edmonds-Karp

A complete run of Edmonds-Karp

Footnotes