Push relabel why return back to source

Question

In push relabel algorithm, at the end excess at any nodes is pushed back to source by raising height of those nodes above the height of source. Why is this done? In CLRS it's mentioned:

To make the preflow a “legal” flow, the algorithm then sends the excess collected in the reservoirs of overflowing vertices back to the source by continuing to relabel vertices to above the fixed height |V| of the source. As we shall see, once we have emptied all the reservoirs, the preflow is not only a “legal” flow, it is also a maximum flow.

What does it mean to say "to make preflow a legal flow". Could someone elaborate on the same.

Answer 1

Inspecting the correctness proof and/or executing any non-trivial example, you'll note that push-relabel algorithms are different from Ford-Fulkerson and variants in that they do not maintain a flow; that's just not part of the invariant, and it's blatantly violated right at the start.

This whole "push flow to the sink, then push the excess back to the source" idea is only that: an idea. The algorithm does not really work like that, always. But it's still useful.

Once the "wave" reaches the sink $t$, it saturates the cut $V \setminus \{t\}$. You still have vertices with excess left¹, though; the conservation of flow property is violated. This has to be remedied before we can terminate with a flow -- hence the "push flow back to the source" phase.

---

1. Whenever the cut $V \setminus \{s\}$ is not by coincidence a min-cut.