node and repeatedly pushes flow from the node until it becomes inactive, relabeling it as necessary to create admissible arcs in the process. discharge(u): while xf[u] > 0 do if current-arc[u] has run off the end of neighbors[u] then relabel(u) rewind current-arc[u] else let (u, v) = current-arc[u] if (u, v) is admissible then push(u, v) let current-arc[u] point to the next neighbor of u Finding the next admissible edge to push on has amortized complexity. The current-arc pointer only moves to the next neighbor when the edge to the current neighbor is saturated or non-admissible, and neither of these two properties can change until the active node is relabelled. Therefore, when the pointer runs off, there are no admissible unsaturated edges and we have to relabel the active node , so having moved the pointer times is paid for by the relabel operation. Active node selection rules Definition of the discharge operation reduces the push–relabel algorithm to repeatedly selecting an active node to discharge. Depending on the selection rule, the algorithm exhibits different time complexities. For the sake of brevity, we ignore and when referring to the nodes in the following discussion. FIFO selection rule The FIFO push–relabel algorithm organizes the active nodes into a queue. The initial active nodes can be inserted in arbitrary order. The algorithm always removes the node at the front of the queue for discharging. Whenever an inactive node becomes active, it is appended to the back of the queue. The algorithm has time complexity. Relabel-to-front selection rule The relabel-to-front push–relabel algorithm organizes all nodes into a linked list and maintains the invariant that the list is topologically sorted with respect to the admissible network. The algorithm scans the list from front to back and performs a discharge operation on the current node if it is active. If the node is relabeled, it is moved to the front of the list, and the scan is restarted from the front. The algorithm also has time complexity. Highest label selection rule The highest-label push–relabel algorithm organizes all nodes into buckets indexed by their labels. The algorithm always selects an active node with the largest label to discharge. The algorithm has time complexity. If the lowest-label selection rule is used instead, the time complexity becomes . Implementation techniques Although in the description of the generic push–relabel algorithm above, is set to zero for each node u other