Course contentsShow
← Computer Science
Lesson 1043 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Push-Relabel Algorithm Basics

Learn the alternative approach using preflows, excess, and height functions instead of augmenting paths.

Push-Relabel Algorithm Basics

You'll learn: An alternative maximum flow approach that uses local operations on vertices instead of searching for complete augmenting paths.


A Different Perspective

While Ford-Fulkerson, Edmonds-Karp, and Dinic's algorithms all find augmenting paths from source to sink, the Push-Relabel algorithm takes a fundamentally different approach. Instead of maintaining a valid flow throughout execution, it works with a preflow—a flow that may violate conservation at some vertices.

Core Concepts

Preflow

Unlike a valid flow where what goes in must equal what goes out (except at source/sink), a preflow allows vertices to have excess—more flow coming in than going out. Think of vertices as buckets that can temporarily overflow.

Excess

Each vertex tracks its excess: incoming flow minus outgoing flow. The source starts by pushing out as much flow as possible to neighbors. Vertices with positive excess are "active" and need to discharge their excess somewhere.

Height Function

Each vertex has a height (or label). Flow can only be "pushed" from a higher vertex to a lower adjacent vertex—like water flowing downhill. The source starts at maximum height; the sink stays at height 0. This prevents flow from cycling uselessly.

How It Works

The algorithm repeatedly performs two operations on active vertices:

  • Push: Send excess flow to a lower neighbor if possible
  • Relabel: If no lower neighbors exist, increase the vertex's height

The algorithm terminates when no vertex (except source and sink) has excess.


Key Takeaway: Push-Relabel replaces global augmenting path searches with local push and relabel operations on a preflow, using height functions to guide flow toward the sink like water flowing downhill.