How does the push-relabel max flow algorithm work with max flow?

Question

I read the relevant articles on Wikipedia and TopCoder, and I read what I read, it hardly makes sense.

Edit: After reading the slideshow and re-reading the TopCoder article more thoroughly, I still don't understand when and how re-marking is done.

Answer 1

To understand the push-relabel algorithm, you need to understand the push and relabel operations. The algorithm simply iterates through each of them as long as possible. Also, at some points, while the algorithm is executing a flow through the network, it is not really valid - but it will be at the end.

push (node)

Click if there is more flow entering the node than leaving it, and if it is possible that some of this excess stream will leave the node (some of the outgoing edges have the remaining capacity from the node)

re-designate (node) This causes the excess flow to enter the node, which cannot leave, because all outgoing edges are saturated and spread it back through the incoming edges, so that their outflow can be reduced. This is usually done by preserving the potential or height associated with each node, and you guarantee that the flow will always go down the potentials.