This article needs editing tocomply with Wikipedia'sManual of Style. In particular, it has problems withMOS:FORMULA - avoid mixing<math>...</math> and{{math}} in the same expression. Please helpimprove the content.(July 2025) (Learn how and when to remove this message)

Inmathematical optimization, thepush–relabel algorithm (alternatively,preflow–push algorithm) is an algorithm for computingmaximum flows in aflow 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 usingpush operations under the guidance of an admissible network maintained byrelabel operations. In comparison, theFord–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink.^[1]

The push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has astrongly polynomialO(V ²E) time complexity, which is asymptotically more efficient than theO(VE ²)Edmonds–Karp algorithm.^[2] Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule hasO(V ²√E) time complexity and is generally regarded as the benchmark for maximum flow algorithms.^[3][4] SubcubicO(VElog(V ²/E)) time complexity can be achieved usingdynamic trees,^[2] although in practice it is less efficient.^{[citation needed]}

The push–relabel algorithm has been extended to computeminimum cost flows.^[5] 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.^[4][6]

The concept of a preflow was originally designed byAlexander 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.^[2][7]

The push-relabel algorithm was designed byAndrew V. Goldberg andRobert 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 inO(V ²E) along with aO(V ³) sequential implementation, aO(VE log(V ²/E)) implementation using dynamic trees, and parallel/distributed implementation.^[2][8] As explained in,^[9] Goldberg–Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach andUzi Vishkin.^[10]

Let:

• G = (V,E) be anetwork withcapacity functionc:V ×V →${\displaystyle \mathbb{R}}$_∞,
• F = (G,c,s,t) aflow network, wheres ∈V andt ∈V are chosensource andsink vertices respectively,
• f :V ×V →${\displaystyle \mathbb{R}}$ denote apre-flow inF,
• x_f :V →${\displaystyle \mathbb{R}}$ denote theexcess function with respect to the flowf, defined byx_f (u) = Σ_{v ∈V}f (v,u) − Σ_{v ∈V}f (u,v),
• c_f :V ×V →${\displaystyle \mathbb{R}}$_∞ denote theresidual capacity function with respect to the flowf, defined byc_f (e) =c(e) −f (e),
• E_f ⊂E being the edges wheref <c,

and

• G_f (V,E_f ) denote theresidual network ofG with respect to the flowf.

The push–relabel algorithm uses a nonnegative integer validlabeling function which makes use ofdistance labels, orheights, on nodes to determine which arcs should be selected for the push operation. This labeling function is denoted by𝓁 :V →${\displaystyle \mathbb{N}}$. This function must satisfy the following conditions in order to be considered valid:

Valid labeling:

𝓁(u) ≤ 𝓁(v) + 1 for all(u,v) ∈E_f

Source condition:

𝓁(s) = | V |

Sink conservation:

𝓁(t) = 0

In the algorithm, the label values ofs andt are fixed.𝓁(u) is a lower bound of the unweighted distance fromu tot inG_f  ift is reachable fromu. Ifu has been disconnected fromt, then𝓁(u) − | V | is a lower bound of the unweighted distance fromu tos. As a result, if a valid labeling function exists, there are nos-t paths inG_f  because no such paths can be longer than| V | − 1.

An arc(u,v) ∈E_f  is calledadmissible if𝓁(u) = 𝓁(v) + 1. Theadmissible networkG̃_f (V,Ẽ_f ) is composed of the set of arcse ∈E_f  that are admissible. The admissible network is acyclic.

For a fixed flowf, a vertexv ∉{s, t} is calledactive if it has positive excess with respect tof, i.e.,x_f (u) > 0.

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(s,v) exiting the source, wherev ∈V \ {s}. Similarly, the labels are initialized such that the label at the source is the number of nodes in the graph,𝓁(s) = | V |, 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.

The push operation applies on an admissible out-arc(u,v) of an active nodeu inG_f. It movesmin{x_f (u),c_f (u,v)} units of flow fromu tov.

push(u, v):assert xf[u] > 0 and 𝓁[u] == 𝓁[v] + 1    Δ = min(xf[u], c[u][v] - f[u][v])    f[u][v] += Δ    f[v][u] -= Δ    xf[u] -= Δ    xf[v] += Δ

A push operation that causesf (u,v) to reachc(u,v) is called asaturating 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 anunsaturating ornon-saturating push.

The relabel operation applies on an active nodeu which is neither the source nor the sink without any admissible out-arcs inG_f. It modifies𝓁(u) to be the minimum value such that an admissible out-arc is created. Note that this always increases𝓁(u) and never creates a steep arc, which is an arc(u,v) such thatc_f (u,v) > 0, and𝓁(u) > 𝓁(v) + 1.

relabel(u):assert xf[u] > 0 and 𝓁[u] <= 𝓁[v] for all v such that cf[u][v] > 0    𝓁[u] = 1 + min(𝓁[v] for all v such that cf[u][v] > 0)

After a push or relabel operation,𝓁 remains a valid labeling function with respect tof.

For a push operation on an admissible arc(u,v), it may add an arc(v,u) toE_f, where𝓁(v) = 𝓁(u) − 1 ≤ 𝓁(u) + 1; it may also remove the arc(u,v) fromE_f, where it effectively removes the constraint𝓁(u) ≤ 𝓁(v) + 1.

To see that a relabel operation on nodeu preserves the validity of𝓁(u), notice that this is trivially guaranteed by definition for the out-arcs ofu inG_f. For the in-arcs ofu inG_f, the increased𝓁(u) can only satisfy the constraints less tightly, not violate them.

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 inO(V²E).

Since𝓁(s) = | V |,𝓁(t) = 0, and there are no paths longer than| V | − 1 inG_f, in order for𝓁(s) to satisfy the valid labeling conditions must be disconnected fromt. At initialisation, the algorithm fulfills this requirement by creating a pre-flowf that saturates all out-arcs ofs, after which𝓁(v) = 0 is trivially valid for allv ∈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 slet 𝓁[s] = |V|let 𝓁[v] = 0 for all v ∈ V \ {s}while there is an applicable push or relabel operationdo        execute the operation

The algorithm maintains the condition that𝓁 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𝓁. The relabel operation increases the label value by the associated minimum plus one which will always satisfy the𝓁(u) ≤ 𝓁(v) + 1 constraint. The push operation can send flow fromu tov if𝓁(u) = 𝓁(v) + 1. This may add(v,u) toG_f  and may delete(u,v) fromG_f . The addition of(v,u) toG_f  will not affect the valid labeling since𝓁(v) = 𝓁(u) − 1. The deletion of(u,v) fromG_f  removes the corresponding constraint since the valid labeling property𝓁(u) ≤ 𝓁(v) + 1 only applies to residual arcs inG_f .^[8]

If a preflowf and a valid labeling𝓁 forf exists then there is no augmenting path froms tot in the residual graphG_f . 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 inV \ {s,t} are not active. This means allv ∈V \ {s,t} have no excess flow, and with no excess the preflowf obeys the flow conservation constraint and can be considered a normal flow. This flow is the maximum flow according to themax-flow min-cut theorem since there is no augmenting path froms tot.^[8]

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

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(2| V | − 1)(| V | − 2) < 2| V |² times. This is because the labeling𝓁(u) value for any nodeu can never decrease, and the maximum label value is at most2| V | − 1 for all nodes. This means the relabel operation could potentially be performed2| V | − 1 times for all nodesV \ {s,t} (i.e.| V | − 2). This results in a bound ofO(V ²) for the relabel operation.

Each saturating push on an admissible arc(u,v) removes the arc fromG_f . For the arc to be reinserted intoG_f  for another saturating push,v must first be relabeled, followed by a push on the arc(v,u), thenu must be relabeled. In the process,𝓁(u) increases by at least two. Therefore, there areO(V) saturating pushes on(u,v), and the total number of saturating pushes is at most2| V || E |. This results in a time bound ofO(VE) for the saturating push operations.

Bounding the number of nonsaturating pushes can be achieved via apotential argument. We use the potential functionΦ = Σ_{[u ∈V ∧xf (u) > 0]} 𝓁(u) (i.e.Φ is the sum of the labels of all active nodes). It is obvious thatΦ is0 initially and stays nonnegative throughout the execution of the algorithm. Both relabels and saturating pushes can increaseΦ. However, the value ofΦ 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Φ to terminate with a value of 0.The relabel operation can increaseΦ by at most(2| V | − 1)(| V | − 2). A saturating push on(u,v) activatesv if it was inactive before the push, increasingΦ by at most2| V | − 1. Hence, the total contribution of all saturating pushes operations toΦ is at most(2| V | − 1)(2| V || E |). A nonsaturating push on(u,v) always deactivatesu, but it can also activatev as in a saturating push. As a result, it decreasesΦ by at least𝓁(u) − 𝓁(v) = 1. Since relabels and saturating pushes increaseΦ, the total number of nonsaturating pushes must make up the difference of(2| V | − 1)(| V | − 2) + (2| V | − 1)(2| V || E |) ≤ 4| V |²| E |. This results in a time bound ofO(V ²E) for the nonsaturating push operations.

In sum, the algorithm executesO(V ²) relabels,O(VE) saturating pushes andO(V ²E) nonsaturating pushes. Data structures can be designed to pick and execute an applicable operation inO(1) time. Therefore, the time complexity of the algorithm isO(V ²E).^[1][8]

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

Initial flow network graph

Final maximum flow network graph

In the example, theh ande values denote the label𝓁 and excessx_f , 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 theperform operation loop.

Algorithm Operation(s)	Residual Graph
Initialise the residual graph by setting the preflow to values 0 and initialising the labeling.
Initial saturating push is performed across all preflow arcs out of the source,s.
Nodea is relabeled in order to push its excess flow towards the sink,t. The excess ata is then pushed tob thend in two subsequent saturating pushes; which still leavesa with some excess.
Once again,a is relabeled in order to push its excess along its last remaining positive residual (i.e. push the excess back tos). The nodea is then removed from the set of active nodes.
Relabelb and then push its excess tot andc.
Relabelc and then push its excess tod.
Relabeld and then push its excess tot.
This leaves the nodeb as the only remaining active node, but it cannot push its excess flow towards the sink. Relabelb and then push its excess towards the source,s, via the nodea.
Push the last bit of excess ata back to the source,s. There are no remaining active nodes. The algorithm terminates and returns the maximum flow of the graph (as seen above).

The example (but with initial flow of 0) can be runhere interactively.

While the generic push–relabel algorithm hasO(V ²E) time complexity, efficient implementations achieveO(V ³) or lower time complexity by enforcing appropriate rules in selecting applicable push and relabel operations. The empirical performance can be further improved by heuristics.

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.

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.

discharge(u):while xf[u] > 0doif current-arc[u] has run off the end of neighbors[u]then            relabel(u)            rewind current-arc[u]elselet (u, v) = current-arc[u]if (u, v) is admissiblethen                push(u, v)let current-arc[u] point to the next neighbor of u

Finding the next admissible edge to push on has${\displaystyle O(1)}$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${\displaystyle u}$ is relabelled. Therefore, when the pointer runs off, there are no admissible unsaturated edges and we have to relabel the active node${\displaystyle u}$, so having moved the pointer${\displaystyle O(V)}$ times is paid for by the${\displaystyle O(V)}$ relabel operation.^[8]

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 ignores andt when referring to the nodes in the following discussion.

TheFIFO push–relabel algorithm^[2] 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 algorithm hasO(V ³) time complexity.

The relabel-to-front push–relabel algorithm^[1] organizes all nodes into a linked list and maintains the invariant that the list istopologically 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 hasO(V ³) time complexity.

The highest-label push–relabel algorithm^[11] organizes all nodes into buckets indexed by their labels. The algorithm always selects an active node with the largest label to discharge.

The algorithm has${\displaystyle O(V\sqrt{E})}$ time complexity. If the lowest-label selection rule is used instead, the time complexity becomesO(V ²E).^[3]

Although in the description of the generic push–relabel algorithm above,𝓁(u) is set to zero for each nodeu other thans andt at the beginning, it is preferable to perform a backwardbreadth-first search fromt to compute exact labels.^[2]

The algorithm is typically separated into two phases. Phase one computes a maximum pre-flow by discharging only active nodes whose labels are belown. Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reacht tos. It can be shown that phase two hasO(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.^[9]

Heuristics are crucial to improving the empirical performance of the algorithm.^[12] Two commonly used heuristics are the gap heuristic and the global relabeling heuristic.^[2][13] The gap heuristic detects gaps in the labeling function. If there is a label0 < 𝓁' < | V | for which there is no nodeu such that𝓁(u) = 𝓁', then any nodeu with𝓁' < 𝓁(u) < | V | has been disconnected fromt and can be relabeled to(| V | + 1) immediately. The global relabeling heuristic periodically performs backward breadth-first search fromt inG_f  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.^[4]

#include<stdlib.h>#include<stdio.h>#define NODES 6#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))#define INFINITE 10000000voidpush(constint*const*C,int**F,int*excess,intu,intv){intsend=MIN(excess[u],C[u][v]-F[u][v]);F[u][v]+=send;F[v][u]-=send;excess[u]-=send;excess[v]+=send;}voidrelabel(constint*const*C,constint*const*F,int*height,intu){intv;intmin_height=INFINITE;for(v=0;v<NODES;v++){if(C[u][v]-F[u][v]>0){min_height=MIN(min_height,height[v]);height[u]=min_height+1;}}};voiddischarge(constint*const*C,int**F,int*excess,int*height,int*seen,intu){while(excess[u]>0){if(seen[u]<NODES){intv=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{relabel(C,F,height,u);seen[u]=0;}}}voidmoveToFront(inti,int*A){inttemp=A[i];intn;for(n=i;n>0;n--){A[n]=A[n-1];}A[0]=temp;}intpushRelabel(constint*const*C,int**F,intsource,intsink){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){intu=list[p];intold_height=height[u];discharge(C,F,excess,height,seen,u);if(height[u]>old_height){moveToFront(p,list);p=0;}else{p+=1;}}intmaxflow=0;for(i=0;i<NODES;i++)maxflow+=F[source][i];free(list);free(seen);free(height);free(excess);returnmaxflow;}voidprintMatrix(constint*const*M){inti,j;for(i=0;i<NODES;i++){for(j=0;j<NODES;j++)printf("%d\t",M[i][j]);printf("\n");}}intmain(void){int**flow,**capacities,i;flow=(int**)calloc(NODES,sizeof(int*));capacities=(int**)calloc(NODES,sizeof(int*));for(i=0;i<NODES;i++){flow[i]=(int*)calloc(NODES,sizeof(int));capacities[i]=(int*)calloc(NODES,sizeof(int));}// Sample graphcapacities[0][1]=2;capacities[0][2]=9;capacities[1][2]=1;capacities[1][3]=0;capacities[1][4]=0;capacities[2][4]=7;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);return0;}

defrelabel_to_front(C,source:int,sink:int)->int:"""Push–relabel maximum flow algorithm."""n=len(C)# C is the capacity matrixF=[[0]*nfor_inrange(n)]# residual capacity from u to v is C[u][v] - F[u][v]height=[0]*n# height of nodeexcess=[0]*n# flow into node minus flow from nodeseen=[0]*n# neighbours seen since last relabel# node "queue"nodelist=[iforiinrange(n)ifi!=sourceandi!=sink]defpush(u,v):send=min(excess[u],C[u][v]-F[u][v])F[u][v]+=sendF[v][u]-=sendexcess[u]-=sendexcess[v]+=senddefrelabel(u):# Find smallest new height making a push possible,# if such a push is possible at all.min_height=∞forvinrange(n):ifC[u][v]-F[u][v]>0:min_height=min(min_height,height[v])height[u]=min_height+1defdischarge(u):whileexcess[u]>0:ifseen[u]<n:# check next neighbourv=seen[u]ifC[u][v]-F[u][v]>0andheight[u]>height[v]:push(u,v)else:seen[u]+=1else:# we have checked all neighbours. must relabelrelabel(u)seen[u]=0height[source]=n# longest path from source to sink is less than n longexcess[source]=∞# send as much flow as possible to neighbours of sourceforvinrange(n):push(source,v)p=0whilep<len(nodelist):u=nodelist[p]old_height=height[u]discharge(u)ifheight[u]>old_height:nodelist.insert(0,nodelist.pop(p))# move to front of listp=0# start from front of listelse:p+=1returnsum(F[source])

• Network flow problem
• Graph algorithms

• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles with style issues from July 2025
• All articles with style issues
• All articles with unsourced statements
• Articles with unsourced statements from December 2024
• Articles with example C code
• Articles with example Python (programming language) code