Downhill Goldberg's push–raise algorithm · ALG 14.5
The source z starts at height n and every edge out of it is filled: that is a preflow. Blue badges show excesses fΔ(v). Your job: get rid of every excess. Click a vertex with excess, then click a lower neighbour to push δ = min(fΔ(u), r(uv)) through the edge, downhill only (h(u) > h(v)). If nothing can go downhill, raise the vertex by one. A vertex's height is its position on the screen.
saturating pushes 0
non-saturating pushes 0
raises 0
flow into s 0
Goldberg: h(z) := n, h(v) := 0 otherwise; f(zv) := c(zv) for all edges from z.
While some u ≠ z, s has fΔ(u) > 0: if some uv has r(uv) > 0 and h(u) > h(v), push through uv; otherwise raise u: h(u) := h(u) + 1.
The analysis in ALG 14.5 bounds the number of raises (heights never exceed 2n), of saturating pushes and of non-saturating pushes separately. Watch the counters above. Non-saturating pushes are the expensive kind.
← ADS2 Arcade
While some u ≠ z, s has fΔ(u) > 0: if some uv has r(uv) > 0 and h(u) > h(v), push through uv; otherwise raise u: h(u) := h(u) + 1.
The analysis in ALG 14.5 bounds the number of raises (heights never exceed 2n), of saturating pushes and of non-saturating pushes separately. Watch the counters above. Non-saturating pushes are the expensive kind.