linguistic:voice_change, information:extraction
Definitions and notations

Let:

and

The push–relabel algorithm uses a nonnegative integer valid labeling function which makes use of distance labels, or heights, on nodes to determine which arcs should be selected for the push operation. This labeling function is denoted by 𝓁 : V → N {\displaystyle \mathbb {N} }. This function must satisfy the following conditions in order to be considered valid:

In the algorithm, the label values of s and t are fixed. 𝓁(u) is a lower bound of the unweighted distance from u to t in G if t is reachable from u. If u has been disconnected from t, then 𝓁(u) − | V | is a lower bound of the unweighted distance from u to s. As a result, if a valid labeling function exists, there are no s - t paths in G because no such paths can be longer than | V | − 1.

An arc (u, v) ∈ E is called admissible if 𝓁(u) = 𝓁(v) + 1. The admissible network G̃ (V, Ẽ) is composed of the set of arcs e ∈ E that are admissible. The admissible network is acyclic.

For a fixed flow f, a vertex v ∉ { s, t } is called active if it has positive excess with respect to f, i.e., x (u) > 0.