# Push-relabel Algorithms

The code for PUSH operates as follows. Vertex *u* is assumed to have a positive excess *e*[*u*], and the residual capacity of (*u*, *v*) is positive. Thus, we can we increase the flow from *u* to *v* by *d _{f}*(

*u*,

*v*) = min(

*e*[

*u*],

*c*(

_{f}*u*,

*v*)) without causing

*e*[

*u*] to become negative or the capacity

*c*(

*u*,

*v*) to be exceeded. Line 3 computes the value

*d*(

_{f}*u*,

*v*), and we update

*f*in lines 4-5 and

*e*in lines 6-7. Thus, if

*f*is a preflow before PUSH is called, it remains a preflow afterward.

Observe that nothing in the code for PUSH depends on the heights of *u* and *v*, yet we prohibit it from being invoked unless *h*[*u*] = *h*[*v*] 1. Thus, excess flow is pushed downhill only by a height differential of 1. By Lemma 26.13, no residual edges exist between two vertices whose heights differ by more than 1, and thus, as long as the attribute *h* is indeed a height function, there is nothing to be gained by allowing flow to be pushed downhill by a height differential of more than 1.

We call the operation PUSH(*u*, *v*) a ** push** from

*u*to

*v*. If a push operation applies to some edge (

*u*,

*v*) leaving a vertex

*u*, we also say that the push operation applies to

*u*. It is a

**if edge (**

*saturating push**u*,

*v*) becomes

**(**

*saturated**c*(

_{f}*u*,

*v*) = 0 afterward); otherwise, it is a

**. If an edge is saturated, it does not appear in the residual network. A simple lemma characterizes one result of a nonsaturating push.**

*nonsaturating push*#### The generic algorithm

The generic push-relabel algorithm uses the following subroutine to create an initial preflow in the flow network.

INITIALIZE-PREFLOW(G,s) 1foreach vertexu∈V[G] 2doh[u] ← 0 3e[u] ← 0 4foreach edge (u,v) ∈E[G] 5dof[u,v] ← 0 6f[v,u] ← 0 7h[s] ← |V[G]| 8foreach vertexu∈Adj[s] 9dof[s,u] ←c(s,u) 10f[u,s] ← -c(s,u) 11e[u] ←c(s,u) 12e[s] ←e[s] -c(s,u)

INITIALIZE-PREFLOW creates an initial preflow *f* defined by

That is, each edge leaving the source *s* is filled to capacity, and all other edges carry no flow. For each vertex *v* adjacent to the source, we initially have *e*[*v*] = *c*(*s*, *v*), and *e*[*s*] is initialized to the negative of the sum of these capacities. The generic algorithm also begins with an initial height function *h*, given by

This is a height function because the only edges (*u*, *v*) for which *h*[*u*] > *h*[*v*] 1 are those for which *u* = *s*, and those edges are saturated, which means that they are not in the residual network.

Initialization, followed by a sequence of push and relabel operations, executed in no particular order, yields the GENERIC-PUSH-RELABEL algorithm:

GENERIC-PUSH-RELABEL(G) 1 INITIALIZE-PREFLOW(G,s) 2whilethere exists an applicable push or relabel operation 3doselect an applicable push or relabel operation and perform it