문제

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.

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top