Push–relabel maximum flow algorithm

A maximum-flow algorithm that maintains a preflow and vertex height labels, pushing excess flow along admissible residual edges and relabeling vertices until all nonterminal excess disappears.

Connect

Preflow: A flow-like assignment that respects capacity constraints but may leave vertices with more inflow than outflow. The algorithm begins with a preflow and routes its excess back toward the source.
Flow network: A directed graph with edge capacities, a source, and a sink, used to model transferable quantities. Push–relabel operates on this capacitated source-to-sink structure.
FIFO push–relabel algorithm: A push–relabel variant that selects active vertices in first-in, first-out order. This common selection rule gives a straightforward implementation with strong practical performance.
Ford–Fulkerson algorithm: A family of maximum-flow methods that repeatedly augments flow along a source-to-sink path in the residual graph. Unlike push–relabel, it maintains a feasible flow after each path augmentation.
Residual graph: A directed graph encoding the remaining capacity for increasing or reversing flow along edges. Pushes use residual capacity, including reverse edges that undo earlier flow.
Flow conservation: The rule that incoming flow equals outgoing flow at every vertex except the source and sink. The algorithm temporarily relaxes conservation at intermediate vertices, then restores it.
Highest-label push–relabel algorithm: A push–relabel variant that processes an active vertex with maximum height at each step. Prioritizing the highest active vertices often reduces work on difficult instances.
Edmonds–Karp algorithm: The Ford–Fulkerson method that chooses shortest residual paths using breadth-first search. Its global path searches contrast with push–relabel's local vertex operations.
Admissible edge: A residual edge from a vertex to a neighbor whose height is exactly one less. Only admissible edges can carry a push under the current height labels.
Capacity constraint: The requirement that flow on an edge cannot exceed its capacity or fall below zero. Every push is bounded by the available residual capacity, preserving feasibility.