Preflowpush

The preflow-push algorithm, also called the push-relabel algorithm, is an algorithm for computing a maximum s-t flow in a directed graph. It maintains a feasible preflow, which allows intermediate vertices to accumulate excess flow, and repeatedly pushes excess toward the sink while possibly increasing the vertices’ height to open new push opportunities.

The method operates on a residual graph and uses two basic operations. A push moves as much flow as possible along a residual edge (u, v) from a vertex u to a neighbor v, subject to the height condition h(u) = h(v) + 1. A relabel operation increases h(u) to the smallest value that enables at least one admissible push given the current residual capacities. Each vertex v has an excess e(v) representing the difference between the inflow and outflow; the source s is initially the sole supplier, and, after initialization, most vertices except s (and later t) may have positive excess.

Initialization saturates all edges out of the source, creating a preflow. The height function is typically initialized with h(s) = |V| and h(v) = 0 for all other vertices. The algorithm terminates when no vertex other than s and t has positive excess; at that point the current flow value equals the total flow out of s (or into t) and is maximal.

As a practical algorithm, the basic version has a worst-case time complexity of O(V^3) with O(E) space. Variants differ in how they select active vertices, including FIFO and highest-label rules, and employ heuristics such as the gap principle and global relabeling to improve performance. The method is widely used in network flow applications and is implemented with adjacency lists and residual capacities to handle large, sparse graphs efficiently.