Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 21:06, 25 November 2013

Revision as of 21:15, 25 November 2013

Line 21:

* <math>\mathrm{excess}(u)</math>. Sum of flow to and from ''u''.

There are three conditions for [[flow network|flow networks]]. After each step of the algorithm, the flow is a '''preflow''', that observes two of the conditions of flow networks, plus a slightly modified third condition:

:{|

* <math>\ f(u,v) \leq c(u,v)</math>. The flow between <math>u</math> and <math>v</math>, does not exceed the capacity.

*| '''Capacity constraints''': || <math>\ f(u,v) =\le - fc(v,u,v)</math>. WeThe maintainflow thealong netan flowedge cannot exceed its capacity.

|-

* <math>\ \sum_v f(v,u) = \mathrm{excess}(u) \geq 0</math> for all nodes <math>u \neq s</math>. Only the source may produce flow.

| '''Skew symmetry''': || <math>\ f(u,v) = - f(v,u)</math>. The net flow from <math>\ u</math> to <math>\ v</math> must be the opposite of the net flow from <math>\ v</math> to <math>\ u</math> (see example).

|-

| '''Flow conservation''': || <math>\ \sum_{w \in V} f(u,w) = 0</math>, unless <math>\ u=s</math> or <math>\ u=t</math>. The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.

|}

The '''preflow''' algorithm observes the first two of the conditions of flow networks, plus a relaxed third condition:

Notice that the last condition for a preflow is relaxed from the corresponding condition for a [[Flow network#Definition|legal flow]] in a regular flow network.

:{|

*| '''Non-negativity constraint: ''' <math>\ \sum_v f(v,u) = \mathrm{excess}(u) \geq 0</math> for all nodes <math>u \neq s</math>. OnlyMore theflow sourceenters maya producenode flowthan exits.

|}

We observe that the longest possible path from ''s'' to ''t'' is <math>|V|</math> nodes long. Therefore it must be possible to assign ''height'' to the nodes such that for any legal flow, <math>\mathrm{height}(s) = |V|</math> and <math>\mathrm{height}(t) = 0</math>, and if there is a positive flow from ''u'' to ''v'', <math>\mathrm{height}(u) > \mathrm{height}(v)</math>. As we adjust the height of the nodes, the flow goes through the network as water through a landscape. Differing from algorithms such as [[Ford–Fulkerson algorithm|Ford–Fulkerson]], the flow through the network is not necessarily a legal flow throughout the execution of the algorithm.