Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 20:18, 26 November 2013

Revision as of 20:32, 26 November 2013

Line 64:

|}

If all these conditions are met we can execute a ''Push'' flow equal to <math>\min(\mathrm{excess}(u), c(u,v)-f(u,v))</math> across the edge <math>(u,v)</math>. .:

Function Push(u,v)

flow = min(excess(u), c(u,v)-f(u,v));

excess(u) -= flow; // subtract the amount of flow moved from the current vertex

excess(v) += flow; // add the flow to the vertex we are pushing to

f(u,v) += flow; // add the amount of flow moved to the flow across the edge ''(u,v)''

f(v,u) -= flow; // subtract the flow from the edge in the other direction.

===Relabel===