Setting

  • The procedure runs on the level graph L, not the full residual graph 59:12, 1:00:07.
  • It is a modified (repeated) DFS from s with three operation types: advance, retreat, augment 59:12, 1:00:07.
  • Keep a "finger" on a current vertex v, reached by DFS from s 1:01:52.

Pseudocode

v ← s;  f ← 0                       # f is the blocking flow being built
while true:
    if v = t:                        # AUGMENT
        b ← min residual capacity on the s–t path found
        add b to f on every edge of that path
        subtract b from those edges' capacities
        delete all now-zero-capacity edges
        v ← s                        # put the finger back on s
    else if some edge (v,u) exists in L:   # ADVANCE
        v ← u
    else:                            # RETREAT
        if v = s: terminate
        let w be the previous vertex; delete edge (w,v); v ← w

1:03:17, 1:04:13, 1:04:51, 1:07:47, 1:08:36

  • Mapping to recursive DFS: a recursive call = advance; returning to the parent = retreat (delete the edge you came back over); reaching t = augment along the call stack 1:04:51, 1:06:19, 1:06:43.
  • In the unit-capacity case, augmenting zeroes every edge on the path, so they are all deleted at once 1:03:17.

Two clarifications the class pressed on

  • "Delete" is local bookkeeping. Edges are removed from consideration inside the blocking-flow subroutine only — nothing is deleted from the actual graph 1:06:43, 1:07:14.
  • No edges get reversed here. The subroutine works entirely within the fixed graph L; it builds a flow rather than augmenting the real flow, so the residual graph does not change mid-subroutine 1:08:36, 1:08:51.
  • Dead ends stay dead. Since capacities only decrease and edges only disappear, a vertex with no path to t now will never gain one later — so deleting all edges into a dead-end vertex is safe 1:07:14, 1:09:14, 1:09:38.
  • No cycles to worry about: L is a DAG (edges only go one level forward), so "already-visited vertex" concerns from general DFS do not arise 1:11:42, 1:12:23.
  • A "dead end" can mean no outgoing edge, or outgoing edges whose endpoints were already explored 1:11:14.

Running time — unit capacity

  • Each edge is examined O(1) times 1:13:31, 1:14:16:
    • advanced on once;
    • then either retreated over (and deleted forever), or reached t and got saturated/added to f (and deleted).
  • ⇒ O(m) per blocking flow 1:14:16.
  • Combined with the ≤ n iteration bound: O(mn) max flow in unit-capacity graphs 1:14:16, 1:14:58.