Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 20:51, 26 November 2013

Latest revision as of 19:05, 30 July 2025

(167 intermediate revisions by 68 users not shown)

Line 1:

{{Short description|Algorithm in mathematical optimization}}

The '''push–relabel algorithm''' is one of the most efficient algorithms to compute a [[maximum flow problem|maximum flow]]. The general algorithm has <math>O(V^2 E)</math> time complexity, while the implementation with FIFO vertex selection rule has <math>O(V^3)</math> running time, the highest active vertex selection rule provides <math>O(V^2\sqrt{E})</math> complexity, and the implementation with [[Daniel Sleator|Sleator]]'s and [[Tarjan]]'s [[Link/cut tree|dynamic tree]] data structure runs in <math>O(V E \log(V^2/E))</math> time. Asymptotically, it is more efficient than the [[Edmonds–Karp algorithm]], which runs in <math>O(VE^2)</math> time.

{{MOS|article|date=July 2025| [[MOS:FORMULA]] - avoid mixing {{tag|math}} and {{tl|math}} in the same expression}}

In [[mathematical optimization]], the '''push–relabel algorithm''' (alternatively, '''preflow–push algorithm''') is an algorithm for computing [[maximum flow]]s in a [[flow network]]. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using ''push'' operations under the guidance of an admissible network maintained by ''relabel'' operations. In comparison, the [[Ford–Fulkerson algorithm]] performs global augmentations that send flow following paths from the source all the way to the sink.<ref name="clrs26"/>

The push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a [[strongly polynomial]] {{math|''O''(''V''^&nbsp;2''E'')}} time complexity, which is asymptotically more efficient than the {{math|''O''(''VE''^&nbsp;2)}} [[Edmonds–Karp algorithm]].<ref name="goldberg86"/> Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule has {{math|''O''(''V''^&nbsp;2{{sqrt|''E''}})}} time complexity and is generally regarded as the benchmark for maximum flow algorithms.<ref name="ahuja97"/><ref name="goldberg08"/> Subcubic {{math|''O''(''VE''log(''V''^&nbsp;2/''E''))}} time complexity can be achieved using [[Link-cut tree|dynamic trees]],<ref name="goldberg86"/> although in practice it is less efficient.{{reference needed|date=December 2024}}

==Overview==

The push–relabel algorithm has been extended to compute [[minimum cost flow]]s.<ref name="goldberg97"/> The idea of distance labels has led to a more efficient augmenting path algorithm, which in turn can be incorporated back into the push–relabel algorithm to create a variant with even higher empirical performance.<ref name="goldberg08"/><ref name="ahuja91"/>

In a flow network, flow going into a vertex must equal flow going out of a vertex (with

the exception of the source node and the sink node, ''s'' and ''t'' respectively). Thus we cannot

accumulate flow anywhere in the network.

==History==

The Preflow algorithm relaxes this constraint while it determines the maximum flow of the network, allowing a vertex to have more flow coming

into it than going out. This is called the ''excess'' flow of a vertex, or ''preflow''. Any vertex with excess flow

is known as an ''active vertex''. Excess flow can only be moved down [[residual graph|residual edges]] of the [[residual graph]]. Flow is ''pushed'' through the network by adjusting the ''height'' of the vertices. Height is updated and maintained via the concept of a ''valid labelling''. Stated precisely this labelling is <math>h(u) \leq h(v) +1</math>, where ''h(u)'' is height of vertex ''u'', for each residual edge incident to ''u''. In other words a vertex cannot be more than 1 higher from its neighbour on a residual edge (there is no bound on how much lower it can be).

Flow always goes from a higher vertex to a lower vertex.

The concept of a preflow was originally designed by [[Alexander V. Karzanov]] and was published in 1974 in Soviet Mathematical Dokladi 15. This pre-flow algorithm also used a push operation; however, it used distances in the auxiliary network to determine where to push the flow instead of a labeling system.<ref name="goldberg86"/><ref name="goldberg2014"/>

To ''push'' preflow is to move it down a residual edge from a vertex ''u'' to a vertex ''v'', where <math>h(u) = h(v)+1 </math>. It is called a ''saturating push'' if all of the capacity of the residual edge was used (and thus the edge ''(u,v)'' is removed from the residual graph). It is called a ''non-saturating push'' if after the push there is still available capacity on edge ''(u,v)''. Note that a non-saturating push will deplete all the excess flow from vertex ''u''. A saturating push may deplete ''u'', but not necessarily.

The push-relabel algorithm was designed by [[Andrew V. Goldberg]] and [[Robert Tarjan]]. The algorithm was initially presented in November 1986 in STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, and then officially in October 1988 as an article in the Journal of the ACM. Both papers detail a generic form of the algorithm terminating in {{math|''O''(''V''^&nbsp;2''E'')}} along with a {{math|''O''(''V''^&nbsp;3)}} sequential implementation, a {{math|''O''(''VE''&nbsp;log(''V''^&nbsp;2/''E''))}} implementation using dynamic trees, and parallel/distributed implementation.<ref name="goldberg86"/><ref name="goldberg88"/> As explained in,<ref name="amo93"/> Goldberg-Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and [[Uzi Vishkin]].<ref name="sv82"/>

==Definition==

==Concepts==

The push-relabel algorithm finds maximum flow on a [[flow network|flow network]]. There are three conditions for a flow network:

===Definitions and notations===

:{|

{{main|Flow network}}

| '''Capacity constraints''': || <math>\ f(u,v) \le c(u,v)</math>. The flow along an edge cannot exceed its capacity.

|-

| '''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.

|}

Let:

The '''preflow''' algorithm observes the first two of the conditions of flow networks, plus a relaxed third condition for the duration of the algorithm (the algorithm finishes once all the excess is gone from the graph, at which point we have a legal flow, and the '''Flow conservation''' constraint is again observed):

*{{math|''G'' {{=}} (''V'', ''E'')}} be a ''network'' with ''capacity function'' {{math|''c'': ''V'' × ''V'' → <math>\mathbb{R}</math>_∞}},

*{{math|''F'' {{=}} (''G'', ''c'', ''s'', ''t'')}} a ''flow network'', where {{math|''s'' ∈ ''V''}} and {{math|''t'' ∈ ''V''}} are chosen ''source'' and ''sink'' vertices respectively,

*{{math|''f'' : ''V'' × ''V'' → <math>\mathbb{R}</math>}} denote a [[Flow network#Flows|''pre-flow'']] in {{mvar|F}},

*{{math|''x''_''f'' : ''V'' → <math>\mathbb{R}</math>}} denote the ''excess'' function with respect to the flow {{mvar|f}}, defined by {{math|''x''_''f'' (''u'') {{=}} Σ_{''v'' ∈ ''V''} ''f'' (''v'', ''u'') − Σ_{''v'' ∈ ''V''} ''f'' (''u'', ''v'')}},

*{{math|''c''_''f'' : ''V'' × ''V'' → <math>\mathbb{R}</math>_∞}} denote the ''residual capacity function'' with respect to the flow {{mvar|f}}, defined by {{math|''c''_''f''&nbsp;(''e'') {{=}} ''c''(''e'') − ''f''&nbsp;(''e'')}},

*{{math|''E''_''f'' ⊂ ''E''}} being the edges where {{math|''f'' < ''c''}},

and

*{{math|''G''_''f'' (''V'', ''E''_''f''&nbsp;)}} denote the [[Flow network#Residuals|''residual network'']] of {{mvar|G}} with respect to the flow {{mvar|f}}.

The push–relabel algorithm uses a nonnegative integer valid '''labeling function''' which makes use of ''distance labels'', or ''heights'', on nodes to determine which arcs should be selected for the push operation. This labeling function is denoted by {{math|𝓁 : ''V'' → <math>\mathbb{N}</math>}}. This function must satisfy the following conditions in order to be considered valid:

:{|

| '''Non-negativity constraint: ''' <math>\ \sum_v f(v,u) = \mathrm{excess}(u) \geq 0</math> for all nodes <math>u \neq s</math>. More flow enters a node than exits.

|}

:'''Valid labeling''':

Given a flow network <math>G(V,E)</math> with capacity from node ''u'' to node ''v'' given as <math>c(u,v)</math>, and the flow across ''u'' and ''v'' given as <math> f(u,v) </math>, source ''s'' and sink ''t'', we want to find the maximum amount of flow you can send from ''s'' to ''t'' through the network. Some key concepts used in the algorithm are:

::{{math|𝓁(''u'') ≤ 𝓁(''v'') + 1}} for all {{math|(''u'', ''v'') ∈ ''E''_''f''}}

:{|

:'''Source condition''':

| '''residual edge''': ||If available capacity <math>c(u,v) - f(u,v)>0</math> we have a residual edge <math>r(u,v)</math>.

::{{math|𝓁(''s'') {{=}} {{!}}&nbsp;''V''&nbsp;{{!}}}}

:'''Sink conservation''':

::{{math|𝓁(''t'') {{=}} 0}}

In the algorithm, the label values of {{mvar|s}} and {{mvar|t}} are fixed. {{math|𝓁(''u'')}} is a lower bound of the unweighted distance from {{mvar|u}} to {{mvar|t}} in {{math|''G''_''f''}}&nbsp; if {{mvar|t}} is reachable from {{mvar|u}}. If {{mvar|u}} has been disconnected from {{mvar|t}}, then {{math|𝓁(''u'') − {{!}}&nbsp;''V''&nbsp;{{!}}}} is a lower bound of the unweighted distance from {{mvar|u}} to {{mvar|s}}. As a result, if a valid labeling function exists, there are no {{math|''s''-''t''}} paths in {{math|''G''_''f''}}&nbsp; because no such paths can be longer than {{math|{{!}}&nbsp;''V''&nbsp;{{!}} − 1}}.

An arc {{math|(''u'', ''v'') ∈ ''E''_''f''}}&nbsp; is called '''admissible''' if {{math|𝓁(''u'') {{=}} 𝓁(''v'') + 1}}. The '''admissible network''' {{math|''G̃''_''f'' (''V'', ''Ẽ''_''f''&nbsp;)}} is composed of the set of arcs {{math|''e'' ∈ ''E''_''f''}}&nbsp; that are admissible. The admissible network is acyclic.

For a fixed flow {{math|''f''}}, a vertex {{math|''v ∉ ''{''s, t''} }} is called '''active''' if it has positive excess with respect to {{math|''f''}}, i.e., {{math|''x''_''f'' (''u'') > 0}}.

===Operations===

====Initialization====

The algorithm starts by creating a residual graph, initializing the preflow values to zero and performing a set of saturating push operations on residual arcs {{math|(''s'', ''v'')}} exiting the source, where {{math|''v'' ∈ ''V'' \ {{(}}''s''{{)}}}}. Similarly, the labels are initialized such that the label at the source is the number of nodes in the graph, {{math|𝓁(''s'') {{=}} {{!}}&nbsp;''V''&nbsp;{{!}}}}, and all other nodes are given a label of zero. Once the initialization is complete the algorithm repeatedly performs either the push or relabel operations against active nodes until no applicable operation can be performed.

====Push====

The push operation applies on an admissible out-arc {{math|(''u'', ''v'')}} of an active node {{mvar|u}} in {{math|''G''_''f''}}. It moves {{math|min{{(}}''x''_''f'' (''u''), ''c''_''f'' (''u'',''v''){{)}}}} units of flow from {{mvar|u}} to {{mvar|v}}.

push(u, v):

assert x_f[u] > 0 and 𝓁[u] == 𝓁[v] + 1

Δ = min(x_f[u], c[u][v] - f[u][v])

f[u][v] += Δ

f[v][u] -= Δ

x_f[u] -= Δ

x_f[v] += Δ

A push operation that causes {{math|''f''&nbsp;(''u'', ''v'')}} to reach {{math|''c''(''u'', ''v'')}} is called a '''saturating push''' since it uses up all the available capacity of the residual arc. Otherwise, all of the excess at the node is pushed across the residual arc. This is called an '''unsaturating''' or '''non-saturating push'''.

====Relabel====

The relabel operation applies on an active node {{mvar|u}} which is neither the source nor the sink without any admissible out-arcs in {{math|''G_f''}}. It modifies {{math|𝓁(''u'')}} to be the minimum value such that an admissible out-arc is created. Note that this always increases {{math|𝓁(''u'')}} and never creates a steep arc, which is an arc {{math|(''u'', ''v'')}} such that {{math|''c''_''f''&nbsp;(''u'', ''v'') > 0}}, and {{math|𝓁(''u'') > 𝓁(''v'') + 1}}.

relabel(u):

assert x_f[u] > 0 and 𝓁[u] <= 𝓁[v] for all v such that c_f[u][v] > 0

𝓁[u] = 1 + min(𝓁[v] for all v such that c_f[u][v] > 0)

====Effects of push and relabel====

After a push or relabel operation, {{math|𝓁}} remains a valid labeling function with respect to {{mvar|f}}.

For a push operation on an admissible arc {{math|(''u'', ''v'')}}, it may add an arc {{math|(''v'', ''u'')}} to {{math|''E_f''}}, where {{math|𝓁(''v'') {{=}} 𝓁(''u'') − 1 ≤ 𝓁(''u'') + 1}}; it may also remove the arc {{math|(''u'', ''v'')}} from {{math|''E''_''f''}}, where it effectively removes the constraint {{math|𝓁(''u'') ≤ 𝓁(''v'') + 1}}.

To see that a relabel operation on node {{mvar|u}} preserves the validity of {{math|𝓁(''u'')}}, notice that this is trivially guaranteed by definition for the out-arcs of ''u'' in {{math|''G''_''f''}}. For the in-arcs of {{mvar|u}} in {{math|''G''_''f''}}, the increased {{math|𝓁(''u'')}} can only satisfy the constraints less tightly, not violate them.

==The generic push–relabel algorithm==

The generic push–relabel algorithm is used as a proof of concept only and does not contain implementation details on how to select an active node for the push and relabel operations. This generic version of the algorithm will terminate in {{math|''O''(''V''²''E'')}}.

Since {{math|𝓁(''s'') {{=}} {{!}}&nbsp;''V''&nbsp;{{!}}}}, {{math|𝓁(''t'') {{=}} 0}}, and there are no paths longer than {{math|{{!}}&nbsp;''V''&nbsp;{{!}} − 1}} in {{math|''G''_''f''}}, in order for {{math|𝓁(''s'')}} to satisfy the valid labeling condition {{mvar|s}} must be disconnected from {{mvar|t}}. At initialisation, the algorithm fulfills this requirement by creating a pre-flow {{mvar|f}} that saturates all out-arcs of {{mvar|s}}, after which {{math|𝓁(''v'') {{=}} 0}} is trivially valid for all {{math|''v'' ∈ ''V'' \ {{(}}''s'', ''t''{{)}}}}. After initialisation, the algorithm repeatedly executes an applicable push or relabel operation until no such operations apply, at which point the pre-flow has been converted into a maximum flow.

generic-push-relabel(G, c, s, t):

create a pre-flow f that saturates all out-arcs of s

'''let''' 𝓁[s] = |V|

'''let''' 𝓁[v] = 0 for all v ∈ V \ {s}

'''while''' there is an applicable push or relabel operation '''do'''

execute the operation

===Correctness===

The algorithm maintains the condition that {{math|𝓁}} is a valid labeling during its execution. This can be proven true by examining the effects of the push and relabel operations on the label function {{math|𝓁}}. The relabel operation increases the label value by the associated minimum plus one which will always satisfy the {{math|𝓁(''u'') ≤ 𝓁(''v'') + 1}} constraint. The push operation can send flow from {{mvar|u}} to {{mvar|v}} if {{math|𝓁(''u'') {{=}} 𝓁(''v'') + 1}}. This may add {{math|(''v'', ''u'')}} to {{math|''G''_''f''&nbsp;}} and may delete {{math|(''u'', ''v'')}} from {{math|''G''_''f''&nbsp;}}. The addition of {{math|(''v'', ''u'')}} to {{math|''G''_''f''&nbsp;}} will not affect the valid labeling since {{math|𝓁(''v'') {{=}} 𝓁(''u'') − 1}}. The deletion of {{math|(''u'', ''v'')}} from {{math|''G''_''f''&nbsp;}} removes the corresponding constraint since the valid labeling property {{math|𝓁(''u'') ≤ 𝓁(''v'') + 1}} only applies to residual arcs in {{math|''G''_''f''&nbsp;}}.<ref name="goldberg88"/>

If a preflow {{mvar|f}} and a valid labeling {{math|𝓁}} for {{mvar|f}} exists then there is no augmenting path from {{mvar|s}} to {{mvar|t}} in the residual graph {{math|''G''_''f''&nbsp;}}. This can be proven by contradiction based on inequalities which arise in the labeling function when supposing that an augmenting path does exist. If the algorithm terminates, then all nodes in {{math|''V'' \ {{(}}''s'', ''t''{{)}}}} are not active. This means all {{math|''v'' ∈ ''V'' \ {{(}}''s'', ''t''{{)}}}} have no excess flow, and with no excess the preflow {{mvar|f}} obeys the flow conservation constraint and can be considered a normal flow. This flow is the maximum flow according to the [[max-flow min-cut theorem]] since there is no augmenting path from {{mvar|s}} to {{mvar|t}}.<ref name="goldberg88"/>

Therefore, the algorithm will return the maximum flow upon termination.

===Time complexity===

In order to bound the time complexity of the algorithm, we must analyze the number of push and relabel operations which occur within the main loop. The numbers of relabel, saturating push and nonsaturating push operations are analyzed separately.

In the algorithm, the relabel operation can be performed at most {{math|(2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)({{!}}&nbsp;''V''&nbsp;{{!}} − 2) < 2{{!}}&nbsp;''V''&nbsp;{{!}}²}} times. This is because the labeling {{math|𝓁(''u'')}} value for any node ''u'' can never decrease, and the maximum label value is at most {{math|2{{!}}&nbsp;''V''&nbsp;{{!}} − 1}} for all nodes. This means the relabel operation could potentially be performed {{math|2{{!}}&nbsp;''V''&nbsp;{{!}} − 1 }} times for all nodes {{math|''V'' \ {{(}}''s'', ''t''{{)}}}} (i.e. {{math|{{!}}&nbsp;''V''&nbsp;{{!}} − 2}}). This results in a bound of {{math|''O''(''V''^&nbsp;2)}} for the relabel operation.

Each saturating push on an admissible arc {{math|(''u'', ''v'')}} removes the arc from {{math|''G''_''f''&nbsp;}}. For the arc to be reinserted into {{math|''G''_''f''&nbsp;}} for another saturating push, {{mvar|v}} must first be relabeled, followed by a push on the arc {{math|(''v'', ''u'')}}, then {{mvar|u}} must be relabeled. In the process, {{math|𝓁(''u'')}} increases by at least two. Therefore, there are {{math|''O''(''V'')}} saturating pushes on {{math|(''u'', ''v'')}}, and the total number of saturating pushes is at most {{math|2{{!}}&nbsp;''V''&nbsp;{{!}}{{!}}&nbsp;''E''&nbsp;{{!}}}}. This results in a time bound of {{math|''O''(''VE'')}} for the saturating push operations.

Bounding the number of nonsaturating pushes can be achieved via a [[Potential method|potential argument]]. We use the potential function {{math|Φ {{=}} Σ_{[''u'' ∈ ''V'' ∧ ''x''_''f''&nbsp;(''u'') > 0]} 𝓁(''u'')}} (i.e. {{math|Φ}} is the sum of the labels of all active nodes). It is obvious that {{math|Φ}} is {{math|0}} initially and stays nonnegative throughout the execution of the algorithm. Both relabels and saturating pushes can increase {{math|Φ}}. However, the value of {{math|Φ}} must be equal to 0 at termination since there cannot be any remaining active nodes at the end of the algorithm's execution. This means that over the execution of the algorithm, the nonsaturating pushes must make up the difference of the relabel and saturating push operations in order for {{math|Φ}} to terminate with a value of 0.

The relabel operation can increase {{math|Φ}} by at most {{math|(2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)({{!}}&nbsp;''V''&nbsp;{{!}} − 2)}}. A saturating push on {{math|(''u'', ''v'')}} activates {{mvar|v}} if it was inactive before the push, increasing {{math|Φ}} by at most {{math|2{{!}}&nbsp;''V''&nbsp;{{!}} − 1}}. Hence, the total contribution of all saturating pushes operations to {{math|Φ}} is at most {{math|(2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)(2{{!}}&nbsp;''V''&nbsp;{{!}}{{!}}&nbsp;''E''&nbsp;{{!}})}}. A nonsaturating push on {{math|(''u'', ''v'')}} always deactivates {{mvar|u}}, but it can also activate {{mvar|v}} as in a saturating push. As a result, it decreases {{math|Φ}} by at least {{math|𝓁(''u'') − 𝓁(''v'') {{=}} 1}}. Since relabels and saturating pushes increase {{math|Φ}}, the total number of nonsaturating pushes must make up the difference of {{math|(2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)({{!}}&nbsp;''V''&nbsp;{{!}} − 2) + (2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)(2{{!}}&nbsp;''V''&nbsp;{{!}}{{!}}&nbsp;''E''&nbsp;{{!}}) ≤ 4{{!}}&nbsp;''V''&nbsp;{{!}}²{{!}}&nbsp;''E''&nbsp;{{!}}}}. This results in a time bound of {{math|''O''(''V''^&nbsp;2''E'')}} for the nonsaturating push operations.

In sum, the algorithm executes {{math|''O''(''V''^&nbsp;2)}} relabels, {{math|''O''(''VE'')}} saturating pushes and {{math|''O''(''V''^&nbsp;2''E'')}} nonsaturating pushes. Data structures can be designed to pick and execute an applicable operation in {{math|''O''(1)}} time. Therefore, the time complexity of the algorithm is {{math|''O''(''V''^&nbsp;2''E'')}}.<ref name="clrs26"/><ref name="goldberg88"/>

===Example===

The following is a sample execution of the generic push-relabel algorithm, as defined above, on the following simple network flow graph diagram.

{{multiple image

| align = center

| width = 350

| image1 = Push Relabel Algoritm Example - Initial Graph.svg

| alt1 = Initial flow network graph

| caption1 = Initial flow network graph

| image2 = Push-Relabel Algorithm Example - Final Network Graph.svg

| alt2 = Final maximum flow network graph

| caption2 = Final maximum flow network graph

}}

{{clear}}

In the example, the {{nowrap|''h''}} and {{nowrap|''e''}} values denote the label {{math|𝓁}} and excess {{math|''x''_''f''&nbsp;}}, respectively, of the node during the execution of the algorithm. Each residual graph in the example only contains the residual arcs with a capacity larger than zero. Each residual graph may contain multiple iterations of the {{nowrap|''perform operation''}} loop.

{{clear}}

{| class="wikitable"

|-

! Algorithm Operation(s) !! Residual Graph

| '''residual edge (Alternate)''': ||<math>r(v,u) = - f (u,v)</math>. We can push flow back along an edge.

|-

| Initialise the residual graph by setting the preflow to values 0 and initialising the labeling. || [[File:Push-Relabel Algorithm Example - Step 1.svg|Step 1|350px]]

| '''residual graph''': ||The set of all residual edges forms the residual graph.

|-

| Initial saturating push is performed across all preflow arcs out of the source, {{mvar|s}}. || [[File:Push-Relabel Algorithm Example - Step 2.svg|Step 2|350px]]

| '''legal labelling''': ||For each residual edge <math>(u,v), \mathrm{height}(u) \leq \mathrm{height}(v) +1 </math>. We only ''push'' from ''u'' to ''v'' if <math>\mathrm{height}(u) = \mathrm{height}(v)+1</math>.

|-

|rowspan="2"| Node {{mvar|a}} is relabeled in order to push its excess flow towards the sink, {{mvar|t}}.

| '''excess(u)''':|| Sum of flow to and from ''u''.

The excess at {{mvar|a}} is then pushed to {{mvar|b}} then {{mvar|d}} in two subsequent saturating pushes; which still leaves {{mvar|a}} with some excess.

|-

| [[File:Push-Relabel Algorithm Example - Step 3.svg|Step 3|350px]]

| '''height(u)''':|| Each vertex is assigned a height value. For values <math>\leq |V|</math>, the height serves as an estimate of the distance to the sink node ''t''. For values <math> > |V|</math>, the height is an estimate of the distance back to the sink ''s''.

|}-

|rowspan="2"| Once again, {{mvar|a}} is relabeled in order to push its excess along its last remaining positive residual (i.e. push the excess back to {{mvar|s}}).

The node {{mvar|a}} is then removed from the set of active nodes.

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.

|-

| [[File:Push-Relabel Algorithm Example - Step 4.svg|Step 4|350px]]

==Algorithm==

|-

The heights of active vertices are raised just enough to send flow into neighbouring vertices, until all possible flow has reached ''t''. Then we continue increasing the height of internal nodes until all the flow that went into the network, but did not reach ''t'', has flowed back into ''s''. A node can reach the height <math>2|V|-1</math> before this is complete, as the longest possible path back to ''s'' excluding ''t'' is <math>|V|-1</math> long, and <math>\mathrm{height}(s) = |V|</math>. The height of ''t'' is kept at 0.

| Relabel {{mvar|b}} and then push its excess to {{mvar|t}} and {{mvar|c}}. || [[File:Push-Relabel Algorithm Example - Step 5.svg|Step 5|350px]]

|-

Once we move all the flow we can to ''t'', there is no more path in the residual graph from ''s'' to ''t'' (in fact this is true as soon as we saturate the min-cut). This means that once the remaining excess flows back to ''s'' not only do we have a legal flow, but we have a maximum flow by the [[max-flow min-cut theorem]]. The algorithm relies on two functions:

| Relabel {{mvar|c}} and then push its excess to {{mvar|d}}. || [[File:Push-Relabel Algorithm Example - Step 6.svg|Step 6|350px]]

|-

===Push===

| Relabel {{mvar|d}} and then push its excess to {{mvar|t}}. || [[File:Push-Relabel Algorithm Example - Step 7.svg|Step 7|350px]]

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:

:{|-

|rowspan="2"| This leaves the node {{mvar|b}} as the only remaining active node, but it cannot push its excess flow towards the sink.

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

Relabel {{mvar|b}} and then push its excess towards the source, {{mvar|s}}, via the node {{mvar|a}}.

|-

| [[File:Push-Relabel Algorithm Example - Step 8.svg|Step 8|350px]]

|-

|rowspan="2"| Push the last bit of excess at {{mvar|a}} back to the source, {{mvar|s}}.

| <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>

There are no remaining active nodes. The algorithm terminates and returns the maximum flow of the graph (as seen above).

|-

| [[File:Push-Relabel Algorithm Example - Step 9.svg|Step 9|350px]]

| <math>\mathrm{height}(u) = \mathrm{height}(v)+1</math> || ''u'' is higher than ''v''.

|}

The example (but with initial flow of 0) can be run [http://www.adrian-haarbach.de/idp-graph-algorithms/implementation/maxflow-push-relabel/index_en.html here] interactively.

If all these conditions are met we can execute a ''Push'':

==Practical implementations==

Function Push(u,v)

While the generic push–relabel algorithm has {{math|''O''(''V''^&nbsp;2''E'')}} time complexity, efficient implementations achieve {{math|''O''(''V''^&nbsp;3)}} or lower time complexity by enforcing appropriate rules in selecting applicable push and relabel operations. The empirical performance can be further improved by heuristics.

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.

==="Current-arc" data structure and discharge operation===

===Relabel===

The "current-arc" data structure is a mechanism for visiting the in- and out-neighbors of a node in the flow network in a static circular order. If a singly linked list of neighbors is created for a node, the data structure can be as simple as a pointer into the list that steps through the list and rewinds to the head when it runs off the end.

When we ''relabel'' a node ''u'' we increase its height until it is 1 higher than its lowest neighbour in the residual graph. Conditions for a ''relabel'':

Based on the "current-arc" data structure, the discharge operation can be defined. A discharge operation applies on an active node and repeatedly pushes flow from the node until it becomes inactive, relabeling it as necessary to create admissible arcs in the process.

:{|

| <math>u</math> is ''active'' ||

|-

| <math>\mathrm{height}(u) \leq \mathrm{height}(v)</math> where <math> r(u,v) > 0</math>

|}

discharge(u):

So we have excess flow to push, but we not higher than any of our neighbours that have available capacity across their edge. Then we can execute '''Relabel''':

'''while''' x_f[u] > 0 '''do'''

'''if''' current-arc[u] has run off the end of neighbors[u] '''then'''

relabel(u)

rewind current-arc[u]

'''else'''

'''let''' (u, v) = current-arc[u]

'''if''' (u, v) is admissible '''then'''

push(u, v)

'''let''' current-arc[u] point to the next neighbor of u

Finding the next admissible edge to push on has <math>O(1)</math> [[amortized complexity]]. The current-arc pointer only moves to the next neighbor when the edge to the current neighbor is saturated or non-admissible, and neither of these two properties can change until the active node <math>u</math> is relabelled. Therefore, when the pointer runs off, there are no admissible unsaturated edges and we have to relabel the active node <math>u</math>, so having moved the pointer <math>O(V)</math> times is paid for by the <math>O(V)</math> relabel operation.<ref name="goldberg88" />

===Active node selection rules===

Function Relabel(u)

Definition of the discharge operation reduces the push–relabel algorithm to repeatedly selecting an active node to discharge. Depending on the selection rule, the algorithm exhibits different time complexities. For the sake of brevity, we ignore {{mvar|s}} and {{mvar|t}} when referring to the nodes in the following discussion.

height(u) = min(height(v) where r(u,v) > 0) + 1;

====FIFO selection rule====

===Push–relabel algorithm===

The [[FIFO (computing and electronics)|FIFO]] push–relabel algorithm<ref name="goldberg86"/> organizes the active nodes into a queue. The initial active nodes can be inserted in arbitrary order. The algorithm always removes the node at the front of the queue for discharging. Whenever an inactive node becomes active, it is appended to the back of the queue.

The generic ''Push–relabel algorithm'' has the following structure:

Algorithm Push-relabel(G(V,E),s,t)

while ''push'' or ''relabel'' are legal: //in other words while there is excess in the network

Perform a legal push, or

perform a legal relabel;

The algorithm has {{math|''O''(''V''^&nbsp;3)}} time complexity.

Executing these two functions in any order, so long as there remains any active vertices results in termination of the algorithm in a maximum flow. The running time for these algorithms when not observing any order to the Push and Relabel operations is <math>O(V^2 E)</math> (argument omitted). The bottleneck is the number of non-saturating pushes.

====Relabel-to-Frontfront Algorithmselection (FIFO heuristic)rule====

The relabel-to-front push–relabel algorithm<ref name="clrs26"/> organizes all nodes into a linked list and maintains the invariant that the list is [[Topological sorting|topologically sorted]] with respect to the admissible network. The algorithm scans the list from front to back and performs a discharge operation on the current node if it is active. If the node is relabeled, it is moved to the front of the list, and the scan is restarted from the front.

The algorithm also has {{math|''O''(''V''^&nbsp;3)}} time complexity.

The Relabel-to-Front algorithm is a variant of the Push-Relabel algorithm that improves the

running time from <math>O(V^2E)</math> to <math>O(V^3)</math>. It does so by executing Push and

Relabel in a specified order. The main difference is we wish to apply Push and Relabel to a single

vertex until its excess is completely spent. This limits the number of ''non-saturating'' pushes that

we make, which is the main bottle-neck of this algorithm.

====Highest label selection rule====

To do this, we maintain a list of all the vertices in the graph <math> L = V - \{s,t\} </math>, in any

The highest-label push–relabel algorithm<ref name="cheriyan88"/> organizes all nodes into buckets indexed by their labels. The algorithm always selects an active node with the largest label to discharge.

particular order (they will be put in order as the algorithm executes). In addition to this master

list, each vertex maintains a list of its neighbours in the graph, in arbitrary but static order.

These are the vertices it will attempt to push flow to. Then, starting at the first

vertex, we ''Discharge'' a vertex <math>u \in L </math> if it is active. Discharge is detailed below:

The algorithm has {{math|''O''(''V''^&nbsp;2{{sqrt|''E''}})}} time complexity. If the lowest-label selection rule is used instead, the time complexity becomes {{math|''O''(''V''^&nbsp;2''E'')}}.<ref name="ahuja97"/>

===Discharge===

In ''relabel-to-front'', a ''discharge'' on a node ''u'' is the following:

===Implementation techniques===

Function Discharge(u):

Although in the description of the generic push–relabel algorithm above, {{math|𝓁(''u'')}} is set to zero for each node ''u'' other than {{mvar|s}} and {{mvar|t}} at the beginning, it is preferable to perform a backward [[breadth-first search]] from {{mvar|t}} to compute exact labels.<ref name="goldberg86"/>

while excess(u) > 0:

if (u.currentNeighbour != NIL):

push(u, u.currentNeighbour);

u.currentNeighbour = u.nextNeighbour;

else:

relabel(u);

u.currentNeighbour = u.headOfNeighbourList; //start again at the beginning of the neighbour list

The algorithm is typically separated into two phases. Phase one computes a maximum pre-flow by discharging only active nodes whose labels are below {{mvar|n}}. Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reach {{mvar|t}} to {{mvar|s}}. It can be shown that phase two has {{math|''O''(''VE'')}} time complexity regardless of the order of push and relabel operations and is therefore dominated by phase one. Alternatively, it can be implemented using flow decomposition.<ref name="amo93"/>

===Relabel-to-Front===

In the ''relabel-to-front algorithm'', the order of the ''push'' and ''relabel'' operations is given:

Heuristics are crucial to improving the empirical performance of the algorithm.<ref name="cherkassky95"/> Two commonly used heuristics are the gap heuristic and the global relabeling heuristic.<ref name="goldberg86"/><ref name="derigs89"/> The gap heuristic detects gaps in the labeling function. If there is a label {{nowrap|0 < 𝓁''{{'}}'' < {{!}}&nbsp;''V''&nbsp;{{!}}}} for which there is no node {{mvar|u}} such that {{math|𝓁(''u'') {{=}} 𝓁''{{'}}''}}, then any node {{mvar|u}} with {{math|𝓁''{{'}}'' < 𝓁(''u'') < {{!}}&nbsp;''V''&nbsp;{{!}}}} has been disconnected from {{mvar|t}} and can be relabeled to {{math|({{!}}&nbsp;''V''&nbsp;{{!}} + 1)}} immediately. The global relabeling heuristic periodically performs backward breadth-first search from {{mvar|t}} in {{math|''G''_''f''&nbsp;}} to compute the exact labels of the nodes. Both heuristics skip unhelpful relabel operations, which are a bottleneck of the algorithm and contribute to the ineffectiveness of dynamic trees.<ref name="goldberg08"/>

# For each edge incident to <math>s, (s,v)</math>, push flow from ''s'' equal to <math>c(s,v)</math> (saturate the edge).

# Build a list <math>L</math> of all vertices except ''s'' and ''t''.

# For each <math> u \in L</math>:

## ''Discharge'' the current vertex ''u''.

## If the height of ''u'' has changed:

### Move ''u'' to the front of the list ''L''

### Restart the traversal from the element following ''u'' in ''L''.

==Sample implementations==

The running time for ''relabel-to-front'' is <math>O(V^3)</math> (proof omitted). Again the bottleneck is non-saturating pushes, but we have reduced the number. Note that after step 1 there is no path from ''s'' to ''t'' in the residual graph.

{{hidden begin|border=1px #aaa solid|titlestyle=text-align:center|title=[[C (programming language)|C]] implementation}}

<syntaxhighlight lang="c">

==Sample implementation==

[[C (programming language)|C]] implementation:

<source lang="c">

#include <stdlib.h>

#include <stdio.h>

#define NODES 6

#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

#define INFINITE 10000000

void push(const int * const * C, int ** F, int *excess, int u, int v) {

int send = MIN(excess[u], C[u][v] - F[u][v]);

Line 152 ⟶ 227:

excess[v] += send;

}

void relabel(const int * const * C, const int * const * F, int *height, int u) {

int v;

Line 162 ⟶ 237:

}

}

};

void discharge(const int * const * C, int ** F, int *excess, int *height, int *seen, int u) {

while (excess[u] > 0) {

if (seen[u] < NODES) {

int v = seen[u];

if ((C[u][v] - F[u][v] > 0) && (height[u] > height[v])) {

push(C, F, excess, u, v);

} else {

seen[u] += 1;

}

else

seen[u] += 1;

} else {

relabel(C, F, height, u);

Line 179 ⟶ 254:

}

}

void moveToFront(int i, int *A) {

int temp = A[i];

int n;

for (n = i; n > 0; n--) {

A[n] = A[n-1];

}

A[0] = temp;

}

int pushRelabel(const int * const * C, int ** F, int source, int sink) {

int *excess, *height, *list, *seen, i, p;

excess = (int *) calloc(NODES, sizeof(int));

height = (int *) calloc(NODES, sizeof(int));

seen = (int *) calloc(NODES, sizeof(int));

list = (int *) calloc((NODES-2), sizeof(int));

for (i = 0, p = 0; i < NODES; i++){

if ((i != source) && (i != sink)) {

list[p] = i;

p++;

}

}

height[source] = NODES;

excess[source] = INFINITE;

for (i = 0; i < NODES; i++)

push(C, F, excess, source, i);

p = 0;

while (p < NODES - 2) {

Line 216 ⟶ 291:

discharge(C, F, excess, height, seen, u);

if (height[u] > old_height) {

moveToFront(p, list);

p = 0;

} else {

else

p += 1;

}

}

int maxflow = 0;

for (i = 0; i < NODES; i++)

maxflow += F[source][i];

free(list);

free(seen);

free(height);

free(excess);

return maxflow;

}

void printMatrix(const int * const * M) {

int i, j;

for (i = 0; i < NODES; i++) {

for (j = 0; j < NODES; j++)

Line 243 ⟶ 318:

}

}

int main(void) {

int **flow, **capacities, i;

Line 252 ⟶ 327:

capacities[i] = (int *) calloc(NODES, sizeof(int));

}

// Sample graph

capacities[0][1] = 2;

capacities[0][2] = 9;

Line 262 ⟶ 337:

capacities[3][5] = 7;

capacities[4][5] = 4;

printf("Capacity:\n");

printMatrix(capacities);

printf("Max Flow:\n%d\n", pushRelabel(capacities, flow, 0, 5));

printf("Flows:\n");

printMatrix(flow);

return 0;

}

</syntaxhighlight>

</source>

{{hidden end}}

{{hidden begin|border=1px #aaa solid|titlestyle=text-align:center|title=[[Python (programming language)|Python]] implementation:}}

<sourcesyntaxhighlight lang="python">

def relabel_to_front(C, source: int, sink: int) -> int:

n = len(C) # C is the capacity matrix

F = [[0] * n for _ in xrangerange(n)]

# residual capacity from u to v is C[u][v] - F[u][v]

height = [0] * n # height of node

excess = [0] * n # flow into node minus flow from node

seen = [0] * n # neighbours seen since last relabel

# node "queue"

nodelist = [i for i in xrangerange(n) if i != source and i != sink]

def push(u, v):

send = min(excess[u], C[u][v] - F[u][v])

F[u][v] += send

F[v][u] -= send

excess[u] -= send

excess[v] += send

def relabel(u):

# findFind smallest new height making a push possible,

# if such a push is possible at all.

min_height = ∞

for v in xrangerange(n):

if C[u][v] - F[u][v] > 0:

min_height = min(min_height, height[v])

height[u] = min_height + 1

def discharge(u):

while excess[u] > 0:

if seen[u] < n: # check next neighbour

v = seen[u]

if C[u][v] - F[u][v] > 0 and height[u] > height[v]:

push(u, v)

else:

seen[u] += 1

else: # we have checked all neighbours. must relabel

relabel(u)

seen[u] = 0

height[source] = n # longest path from source to sink is less than n long

excess[source] = Inf∞ # send as much flow as possible to neighbours of source

for v in xrangerange(n):

push(source, v)

p = 0

while p < len(nodelist):

u = nodelist[p]

old_height = height[u]

discharge(u)

if height[u] > old_height:

nodelist.insert(0, nodelist.pop(p)) # move to front of list

p = 0 # start from front of list

else:

p += 1

return sum(F[source])

</syntaxhighlight>

</source>

{{hidden end}}

Note that the above implementation is not very efficient. It is slower than [[Edmonds–Karp algorithm]] even for very dense graphs. To speed it up, you can do at least two things:

# Make neighbour lists for each node, and let the index <code>seen[u]</code> be an iterator over this, instead of the range <math>0,\ldots,n-1</math>.

# Use a '''gap heuristic'''. If there is a <math>k</math> such that for no node, <math>\mathrm{height}(u)=k</math>, you can set <math>\mathrm{height}(u)=\max(\mathrm{height}(u), \mathrm{height}(s) + 1)</math> for all nodes except <math>s</math> for which <math>\mathrm{height}(u)>k</math>. This is because any such <math>k</math> represents a [[max-flow min-cut theorem|minimal cut]] in the graph, and no more flow will go from the nodes <math>S = \{u\mid \mathrm{height}(u)>k\}</math> to the nodes <math>T = \{v\mid \mathrm{height}(v)<k\}</math>. If <math>(S,T)</math> was not a minimal cut, there would be an edge <math>(u,v)</math> such that <math>u \in S</math>, <math>v \in T</math> and <math>c(u,v)-f(u,v) > 0</math>. But then <math>\mathrm{height}(u)</math> would never be set higher than <math>\mathrm{height}(v)+1</math>, contradicting that <math>\mathrm{height}(u) > k</math> and <math>\mathrm{height}(v) < k</math>.

== References ==

{{reflist|2|refs=

<ref name="clrs26">{{Cite book | isbn = 978-0262032933 | title = Introduction to Algorithms | edition = 2nd | last1 = Cormen | first1 = T. H. | author-link1 = Thomas H. Cormen | year = 2001 | publisher = The MIT Press | last2 = Leiserson | first2 = C. E. | author-link2 = Charles E. Leiserson | last3 = Rivest | first3 = R. L. | author-link3 = Ron Rivest | last4 = Stein | first4 = C. | author-link4 = Clifford Stein | chapter = §26 Maximum flow | pages = [https://archive.org/details/introductiontoal00corm_691/page/n665 643]–698| title-link = Introduction to Algorithms }}</ref>

<ref name="goldberg86">{{cite book|doi=10.1145/12130.12144|chapter=A new approach to the maximum flow problem|title=Proceedings of the eighteenth annual ACM symposium on Theory of computing – STOC '86|pages=136|year=1986|last1=Goldberg|first1=A V|last2=Tarjan|first2=R E|isbn=978-0897911931|s2cid=14492800}}</ref>

<ref name="goldberg88">{{cite journal|doi=10.1145/48014.61051|title=A new approach to the maximum-flow problem|journal=Journal of the ACM|volume=35|issue=4|pages=921|year=1988|last1=Goldberg|first1=Andrew V.|last2=Tarjan|first2=Robert E.|s2cid=52152408|doi-access=free}}</ref>

<ref name="sv82">{{cite journal|doi=10.1016/0196-6774(82)90013-X|title=An O(n2log n) parallel max-flow algorithm|journal=Journal of Algorithms|volume=3|issue=2|pages=128–146|year=1982|last1=Shiloach|first1=Yossi|last2=Vishkin|first2=Uzi}}</ref>

<ref name="cheriyan88">{{cite book|doi=10.1007/3-540-50517-2_69|chapter=Analysis of preflow push algorithms for maximum network flow|title=Foundations of Software Technology and Theoretical Computer Science|volume=338|pages=30|series=Lecture Notes in Computer Science|year=1988|last1=Cheriyan|first1=J.|last2=Maheshwari|first2=S. N.|isbn=978-3-540-50517-4}}</ref>

<ref name="derigs89">{{cite journal|doi=10.1007/BF01415937|title=Implementing Goldberg's max-flow-algorithm ? A computational investigation|journal=Zeitschrift für Operations Research |volume=33|issue=6|pages=383|year=1989|last1=Derigs|first1=U.|last2=Meier|first2=W.|s2cid=39730584}}</ref>

<ref name="ahuja91">{{cite journal|doi=10.1002/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J|title=Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems|journal=Naval Research Logistics|volume=38|issue=3|pages=413|year=1991|last1=Ahuja|first1=Ravindra K.|last2=Orlin|first2=James B.|citeseerx=10.1.1.297.5698}}</ref>

<ref name="amo93">{{Cite book | isbn = 978-0136175490 | title = Network Flows: Theory, Algorithms, and Applications | edition = 1st | last1 = Ahuja | first1 = R. K. | year = 1993 | publisher = Prentice Hall | last2 = Magnanti | first2 = T. L. | last3 = Orlin | first3 = J. B. }}</ref>

<ref name="cherkassky95">{{cite book|doi=10.1007/3-540-59408-6_49|chapter=On implementing push-relabel method for the maximum flow problem|title=Integer Programming and Combinatorial Optimization|volume=920|pages=157|series=Lecture Notes in Computer Science|year=1995|last1=Cherkassky|first1=Boris V.|last2=Goldberg|first2=Andrew V.|isbn=978-3-540-59408-6|citeseerx=10.1.1.150.3609}}</ref>

<ref name="ahuja97">{{cite journal|doi=10.1016/S0377-2217(96)00269-X|title=Computational investigations of maximum flow algorithms|journal=European Journal of Operational Research|volume=97|issue=3|pages=509|year=1997|last1=Ahuja|first1=Ravindra K.|last2=Kodialam|first2=Murali|last3=Mishra|first3=Ajay K.|last4=Orlin|first4=James B.|citeseerx=10.1.1.297.2945}}</ref>

<ref name="goldberg97">{{cite journal|doi=10.1006/jagm.1995.0805|title=An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm|journal=Journal of Algorithms|volume=22|pages=1–29|year=1997|last1=Goldberg|first1=Andrew V}}</ref>

<ref name="goldberg08">{{cite book|doi=10.1007/978-3-540-87744-8_39|chapter=The Partial Augment–Relabel Algorithm for the Maximum Flow Problem|title=Algorithms – ESA 2008|volume=5193|pages=466–477|series=Lecture Notes in Computer Science|year=2008|last1=Goldberg|first1=Andrew V.|isbn=978-3-540-87743-1|citeseerx=10.1.1.150.5103}}</ref>

<ref name="goldberg2014">{{cite journal|doi=10.1145/2628036|title=Efficient maximum flow algorithms|journal=Communications of the ACM|volume=57|issue=8|pages=82|year=2014|last1=Goldberg|first1=Andrew V.|last2=Tarjan|first2=Robert E.|s2cid=17014879}}</ref>

}}

{{optimization algorithms|combinatorial|state=expanded}}

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Section 26.4: Push–relabel algorithms, and section 26.5: The relabel-to-front-algorithm.

* [[Andrew V. Goldberg]], [[Robert E. Tarjan]]. [http://doi.acm.org/10.1145/12130.12144 A new approach to the maximum flow problem]. Annual ACM Symposium on Theory of Computing, Proceedings of the eighteenth annual ACM symposium on Theory of computing, 136–146. ISBN 0-89791-193-8, 1986

[[Category:Network flow problem]]

{{DEFAULTSORT:Push-relabel maximum flow algorithm}}

[[Category:Network flow]]

[[Category:Graph algorithms]]

[[Category:Articles with example C code]]

[[Category:Articles with example Python (programming language) code]]