Overview
Push-Relabel maintains a preflow and local height labels. Active vertices push excess along admissible edges, and relabeling raises a vertex when no admissible edge remains.
CoreSource checked
Push-Relabel
Computes maximum flow by pushing excess flow from active vertices and raising vertex heights.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Network Flow
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 1
- Relationships
- 7
- Code example
- Ready
- Visualization
- Ready
Core Concepts
maximum flownetwork flowresidual graphgraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E)
Average
O(V^2 E)
Worst
O(V^2 E)
Space
O(V + E)
When to Use
- Use it for maximum-flow problems, especially when local push operations are efficient.
- Use it when high-performance max-flow implementations are available.
- Use gap and global relabel heuristics for practical speed.
When Not to Use
- Avoid it when the problem is not a capacitated directed flow network.
- Avoid it when a simpler augmenting-path method is easier and the graph is tiny.
- Avoid skipping invariant checks while implementing residual capacities.
What It Does
- Computes maximum flow
- Maintains excess flow and height labels
Use Cases
- Dense maximum-flow networks
- Flow problems where push-relabel heuristics perform well
- Comparing max-flow formulations
Inputs
- Directed capacitated graph G = (V, E, c) with source s and sink t
Outputs
- Maximum s-t flow assignment f(u, v) on each edge
- Residual network and minimum-cut partition
Key Formulas (1)
Residual capacity
residual(u,v) = capacity(u,v) − flow(u,v)
residual(u,v) = capacity(u,v) - flow(u,v)A push can send flow only across residual capacity.
Pseudocode
- 1.Initialize a preflow by saturating edges out of the source.
- 2.While there is an active non-source, non-sink vertex:
- 3.If it has an admissible residual edge, push excess along that edge.
- 4.Otherwise relabel the vertex to expose an admissible edge.
- 5.Return the total flow into the sink.
Canonical Example
- Input
- source s connected to a and b, both connected to sink t with capacities
- Output
- maximum s-t flow value
- Explanation
- Excess is pushed from active vertices toward lower-height neighbors until only source and sink hold imbalance.
Implementation Notes
- Initialize by saturating source outgoing edges.
- Keep residual capacity, excess, and height arrays explicit.
- Use global relabeling as an optimization after the basic algorithm is correct.
Common Pitfalls
- Violating capacity or skew-symmetry constraints during push operations.
- Relabeling a vertex without checking all outgoing residual edges.
- Forgetting that intermediate preflows need not conserve flow at active vertices.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow pushing excess flow from active vertices and relabeling heights to expose admissible edges on a small maximum flow example.
Step 1 of 5: Initialize a preflow by saturating edges out of the source.
graph-traversal-mechanismNotes
Push-Relabel operates in O(V^2 E) time and O(V + E) space within the Network Flow family. Key governing relation: residual(u,v) = capacity(u,v) - flow(u,v). Often compared with Ford-Fulkerson and Dinic's Algorithm.
Sources (3)
What each reference supports for this entry.
Network Flows: Theory, Algorithms, and Applications
BookReference for Push-Relabel's network-flow, cut, residual-network, or matching formulation.
Introduction to Algorithms (CLRS)
BookTextbook support for Push-Relabel's algorithm family, complexity framing, and standard implementation concepts.
Open sourceGoldberg-Tarjan Push-Relabel
PaperOriginal reference for preflow-push and relabel operations in maximum-flow algorithms.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toDinic's Algorithm
Graph Traversal · Core
Dinic's algorithm uses blocking flows in level graphs; push-relabel uses local preflow operations.
Compare with thisAlternative toEdmonds-Karp
Graph Traversal · Core
Edmonds-Karp has a simple BFS augmenting-path rule, while push-relabel is often faster on dense networks.
Compare with thisAlternative toFord-Fulkerson
Graph Traversal · Core
Ford-Fulkerson augments complete paths, while push-relabel moves local excess through the residual network.
Compare with thisAlternativesStoer-Wagner Min Cut
Graph Traversal · Core
Both address global minimum cut, but they make different modeling or performance tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toFord-Fulkerson
Ford-Fulkerson augments complete paths, while push-relabel moves local excess through the residual network.
Alternative toDinic's Algorithm
Dinic's algorithm uses blocking flows in level graphs; push-relabel uses local preflow operations.
Alternative toEdmonds-Karp
Edmonds-Karp has a simple BFS augmenting-path rule, while push-relabel is often faster on dense networks.
Related Algorithms
Tags
GraphTraversalNetwork Flow