Skip to content
Tutorials Center
My learning

Topics

Lesson 146 of 225 ยท Shortest Paths and Spanning Trees

Push-Relabel and Min-Cost Flow

Compute maximum flow with push-relabel and minimum-cost flow with successive shortest paths in Python, verified against Edmonds-Karp and brute force.

In Network Flow you pushed flow along whole augmenting paths from the source to the sink (Ford-Fulkerson and Edmonds-Karp). That is natural, but it is not the only way to compute a maximum flow, and it ignores a second question: if several maximum flows exist, which one is cheapest?

This lesson adds two ideas. The push-relabel algorithm (Goldberg and Tarjan) never looks for a path; it floods the network with too much flow at the source and then fixes local imbalances by pushing flow downhill. Its worst-case bound is better than Edmonds-Karp on dense graphs. Then min-cost flow gives each edge a cost per unit and finds the cheapest way to send a required amount of flow, which models transportation, assignment and scheduling problems. Both are checked against simpler algorithms.

Push-relabel: the picture

Think of water in pipes on a hillside. Every node gets a height label h. Initially the source sits at height n (the number of nodes) and everything else at 0. Water (flow) only moves downhill by exactly one level, along an edge that still has room.

  • Excess of a node: flow in minus flow out. A node with positive excess is active (except source and sink).
  • Push from u to v: if u has excess, the edge u -> v has residual capacity and h[u] = h[v] + 1, send min(excess[u], residual).
  • Relabel u: if u has excess but no downhill residual edge, raise h[u] to one more than the lowest neighbor reachable by a residual edge.

First, saturate every edge leaving the source (a "preflow": some nodes now hold more than they can pass on). Then keep discharging active nodes until none remain. Excess that cannot reach the sink climbs until it flows back toward the source, so the preflow turns into a valid flow, and the excess collected at the sink is the maximum flow.

flowchart LR
  S["source (h = n)"] -->|"saturate"| A["a: excess"]
  S -->|"saturate"| B["b: excess"]
  A -->|"push downhill"| T["sink (h = 0)"]
  B -->|"relabel, then push"| A

A node pushes only to a neighbor exactly one level lower; when stuck it relabels (rises).

The generic algorithm does O(V^2 E) operations; the FIFO queue version below runs in O(V^3), and the highest-label variant in O(V^2 sqrt(E)).

Python Push-relabel max flow, checked against Edmonds-Karp

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ptr array is the current-arc optimization: each node remembers which edge it was scanning, so the work per relabel stays small. The code returns the flow value; to read the flow on an edge, compare its residual capacity with the original.

When to prefer which

Algorithm Worst-case time Notes
Edmonds-Karp O(V E^2) simplest to write
Dinic O(V^2 E) fast in practice on unit and bipartite graphs
Push-relabel (FIFO) O(V^3) strong on dense graphs; add gap and global relabeling heuristics for speed
Push-relabel (highest label) O(V^2 sqrt(E)) often the fastest in benchmarks

Min-cost flow

Now give each edge (u, v) a capacity and a cost per unit of flow. Send F units from source to sink (or as much as possible) at minimum total cost.

The standard method is successive shortest paths: repeatedly find the cheapest path from the source to the sink in the residual graph and push as much flow as possible along it. The residual edge of u -> v with cost w is v -> u with cost -w, so residual graphs have negative edges, and we need Bellman-Ford or SPFA for each search. (With potentials you can reuse Dijkstra; the result is the same.)

Why does it work? Each augmentation along a shortest path keeps the flow minimum cost for its current value, and no negative cycles ever appear in the residual graph. The number of augmentations is at most the total flow, so with SPFA the time is about O(F * V * E) in the worst case.

Python Min-cost flow by successive shortest paths

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The assignment problem from Stable Marriage and the Hungarian Algorithm is just min-cost flow on a bipartite graph with unit capacities: source to each worker, each worker to each job with the pair's cost, each job to the sink. The flow solution matches the Hungarian result.

Things min-cost flow models

  • Transportation: factories with supply, shops with demand, edges with shipping cost per unit.
  • Assignment and matching with weights.
  • Scheduling: split work into time slots, with different costs per slot.
  • Minimum-cost circulation and many "choose k disjoint paths" problems (give each node capacity 1 by node-splitting).

If edge costs can be negative, the first search needs Bellman-Ford; after that the residual graph never creates a negative cycle, so SPFA stays safe.

Common mistakes

  • Giving the sink or source active status in push-relabel (never queue them).
  • Forgetting the paired reverse edge with negated cost in min-cost flow.
  • Using Dijkstra without potentials on a residual graph with negative edges.
  • Treating flow == requested as guaranteed: if the network cannot carry that much, the algorithm stops at the maximum possible flow, so always check the returned flow.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In push-relabel, flow can be pushed from u to v only when:

    A push goes downhill by exactly one level along an edge with remaining capacity. Nodes that cannot push relabel to rise.
  2. 2. What is the relabel operation?

    An active node with no downhill residual edge rises just enough to create one.
  3. 3. Why does a min-cost flow edge need a reverse edge with negative cost?

    Undoing a unit of flow on an edge refunds its cost, which is represented by the reverse residual edge with cost -w.
  4. 4. Successive shortest paths for min-cost flow finds each augmenting path using:

    Each augmentation follows the cheapest source-to-sink path in the residual graph, whose edges may have negative costs.

Summary

  • Push-relabel keeps a height per node, saturates source edges, then pushes excess downhill by one level and relabels stuck nodes; FIFO ordering gives O(V^3).
  • Excess that reaches the sink at the end is the maximum flow; cross-check with Edmonds-Karp.
  • Min-cost flow gives edges a cost per unit; successive shortest paths augment along the cheapest residual path, using SPFA or Bellman-Ford for negative residual edges.
  • Assignment, transportation and weighted matching are all min-cost flow problems.
  • Always check how much flow was actually sent.

Next: Eulerian and Hamiltonian Paths