10 Push Relabel Algorithm
This chapter covers
- Calculating maximum flow localized node operations instead of global pathfinding
- Managing preflow, excess capacity, and height functions to govern flow mechanics
- Understanding time and space complexity with algorithmic insights
In Chapter 9, we utilized dynamic programming with the Floyd-Warshall algorithm to construct a precomputed O(1) global lookup table for All-Pairs Shortest Paths. That model assumed static edge weights representing distances or costs. But what happens when edges do not represent static distances but rather carrying capacities, such as gigabits per second in a fiber network, gallons per minute in a pipeline, or pixels in a vision graph?
To determine the absolute maximum throughput a network can sustain from a source to a sink, traditional path-based methods like Ford-Fulkerson repeatedly search for global augmenting paths. When graphs become dense or capacity values scale massively, global path search becomes a computational bottleneck. In this chapter, we abandon global pathfinding entirely. We adopt the Push-Relabel algorithm (also known as the FIFO Preflow algorithm, developed by Andrew V. Goldberg and Robert E. Tarjan), transforming the network into a series of localized, overflowing water reservoirs that self-level using height functions.