How does the push-relabel maximum flow algorithm work?

I read the corresponding articles on Wikipedia and开发者_C百科 TopCoder and I what I read makes barely any sense.

Edit: After reading the slide show and rereading the TopCoder article more carefully, I still don't understand when and how a relabelling is carried out.

In order to understand the push-relabel algorithm you need to understand the push and relabel operations. The algorithm just iterates running each of them while it can. Also at some points while the algorithm executes the flow through the network is not actually valid - but will be at the end.

push(node)

Push checks if there is more flow coming into a node than leaving it and if it is possible for some of this excess flow to leave the node (there is remaining capacity in some of the outgoing edges from that node)

relabel(node) This takes the excess flow coming into a node that cannot leave because all the outgoing edges are saturated and propagates it backwards through the incoming edges so that their outflow can be reduced. This is usually done by storing a potential or height associated with each node, and you ensure that the flow always goes downhill the potentials.