CODEWITHSUNDEEP
algorithmgraph-algorithm
pranpran
pranpran

Reputation: 35

What's the point of the residual graph in the push-relabel algorithm?

I sort of understand how the push-relabel algorithm works. As per my understanding, it works by maintaining a preflow, however this results in there being excess flow at some nodes. Then, on a node with excess, the push operation will either push flow forward if it can, or backwards if it has reached capacity. However, if there are no adjacent nodes of a lower height, it will relabel the node to have a greater height.

I can see how this works on a normal graph. So why even introduce the residual graph? In every explanation of the algorithm I see, these operations are performed on the residual graph, which is confusing to me.

Upvotes: 2

Views: 195

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

The point of the residual graph is that there is no special casing for forward versus backward pushes. All there is is pushing flow on a residual arc from a higher label to a lower one. The way that push-relabel directs flow to the sink is by not allowing the sink's label to increase from zero.

Upvotes: 2

Related Questions