Graph Theory37 sections · 1633 units
Open in Course

Residual Capacity Update

(Forward and backward edges)

When you push flow along an augmenting path, you update two things for each edge (u,v)(u,v) on the path:

1.1. Increase f(u,v)f(u,v) by the bottleneck (forward flow goes up).

2.2. Decrease f(v,u)f(v,u) by the bottleneck (backward flow goes down, or reverse flow increases).

This maintains the residual graph invariant. The forward capacity decreases, and the backward capacity increases by the same amount. You can represent flow implicitly: store only the residual capacities, not the flow values directly.