Residual Network¶

Definition¶

For an original directed edge $i\to j$ with capacity $c_{ij}$ and assigned flow $x_{ij}$ , its residual capacities are $c_{ij}-x_{ij}$ in the forward direction and $x_{ij}$ in the reverse direction. The residual network records these possibilities for increasing or cancelling current flow.

Interpretation¶

The residual network records, for the current flow, how the flow on each edge can still change: how much more can be sent forward, and how much of the present flow can be cancelled. It is the network in which the augmenting path algorithm searches for improvements.

An edge with flow 3 of capacity 4, and its residual version: a forward edge with spare capacity 1 and a backward edge with capacity 3 to undo flow.

The original edge carries flow 3 of capacity 4. In the residual version, the forward edge has capacity $c_{ij}-x_{ij}=1$ $1$ , the room left, and the backward edge has capacity $x_{ij}=3$ $3$ , the flow that could be undone. The two residual capacities always add up to the original capacity, here $1+3=4$ $4$ .

Reverse residual capacity is essential because a good final routing may require undoing part of an initially chosen path. Take a source $S$ , a sink $T$ and vertices $A$ and $B$ , with edges $S\to A$ $A$ , $S\to B$ $B$ , $A\to B$ $B$ , $A\to T$ and $B\to T$ $T$ , all of capacity 1. If the first augmentation sends one unit along $S\to A\to B\to T$ $T$ , no route of forward edges with spare capacity remains. The residual network still has $S\to B$ $B$ , the backward direction $B\to A$ and $A\to T$ $T$ ; sending one unit this way cancels the flow on $A\to B$ and reaches the maximum value 2.

A backward residual edge is neither a new connection in the original directed network nor a negative flow. Using it lowers $x_{ij}$ on the original edge $i\to j$ $j$ , and never below $0$ , because the backward capacity is exactly $x_{ij}$ ; in the same way the forward capacity keeps $x_{ij}\le c_{ij}$ $c_{ij}$ .

Key Results¶

The course draws a connection with two directional residual labels; it must not be interpreted as equal capacity in both directions.
Only directions with positive residual capacity can be used by an augmenting path.
A forward augmentation decreases forward residual capacity and increases reverse residual capacity by the same amount.

Examples¶

A saturated original edge has no forward residual capacity; its backward residual direction permits cancelling its assigned flow.

Capacity 6 and flow 2 on A-B give residual capacities 4 forward and 2 backward.
Cancelling one unit changes those residual capacities to 5 forward and 1 backward.

Prerequisites¶

Maximum Flow Problem

Sources¶

OR Modelling · Week 4

Aliases: residual graph

Last updated: 20 October 2026 03:02