the flow , defined by , denote the residual capacity function with respect to the flow , defined by , being the edges where , and denote the residual network of with respect to the flow . 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 . This function must satisfy the following conditions in order to be considered valid: Valid labeling: for all Source condition: Sink conservation: In the algorithm, the label values of and are fixed. is a lower bound of the unweighted distance from to in if is reachable from . If has been disconnected from , then is a lower bound of the unweighted distance from to . As a result, if a valid labeling function exists, there are no paths in because no such paths can be longer than . An arc is called admissible if . The admissible network is composed of the set of arcs that are admissible. The admissible network is acyclic. For a fixed flow , a vertex is called active if it has positive excess with respect to , i.e., . Operations Initialization The algorithm starts by creating a residual graph, initializing the preflow values to zero and performing a set of saturating push operations on residual arcs exiting the source, . Similarly, the labels are initialized such that the label at the source is the number of nodes in the graph, , and all other nodes are given a label of zero. Once the initialization is complete the algorithm repeatedly performs either the push or relabel operations against active nodes until no applicable operation can be performed. Push The push operation applies on an admissible out-arc of an active node in . It moves units of flow from to . push(u, v): assert xf[u] > 0 and 𝓁[u] == 𝓁[v] + 1 Δ = min(xf[u], c[u][v] - f[u][v]) f[u][v] += Δ f[v][u] -= Δ xf[u] -= Δ xf[v] += Δ A push operation that causes to reach is called a saturating push since it uses up all the available capacity of the residual arc. Otherwise, all of the excess at the node is pushed across the residual arc. This is called an unsaturating or non-saturating push. Relabel The relabel operation applies