Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 12:48, 27 November 2013

Revision as of 12:53, 27 November 2013

Line 57:

A ''push'' from ''u'' to ''v'' means sending as much excess flow from ''u'' to ''v'' as we can. Three conditions must be met for a ''push'' to take place:

:{|

| <math>u</math> is active || Which meansOr <math>\mathrm{excess}(u) > 0</math>. There is more flow entering than exiting the vertex.

|-

| <math>r(u,v) > 0</math> || There is a residual edge <math>r(u,v)</math> from ''u'' to ''v'', where <math>r(u,v) = c(u,v) - f(u,v)</math>

|-

| style = "width:300px" | <math>\mathrm{height}(u) = \mathrm{height}(v)+1</math> || ''u'' is higher than ''v''.

|}