{"history":[],"article":{"id":"8085b941-d18c-49f8-b32e-54c2333013dc","title":"Push–relabel maximum flow algorithm","slug":"push-relabel-maximum-flow-algorithm","content":":::summary\n:::\n\n# \nIn [mathematical optimization](https://bliptext.com/articles/mathematical-optimization), the **push–relabel algorithm** (alternatively, **preflow–push algorithm**) is an algorithm for computing [maximum flows](https://bliptext.com/articles/maximum-flow) in a [flow network](https://bliptext.com/articles/flow-network).\nThe name \"push–relabel\" comes from the two basic operations used in the algorithm.\nThroughout 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.\nIn comparison, the [Ford–Fulkerson algorithm](https://bliptext.com/articles/ford-fulkerson-algorithm) performs global augmentations that send flow following paths from the source all the way to the sink.\nThe push–relabel algorithm is considered one of the most efficient maximum flow algorithms.\nThe generic algorithm has a [strongly polynomial](https://bliptext.com/articles/strongly-polynomial)\nO(V2E)\ntime complexity, which is asymptotically more efficient than the\nO(VE2)\n[Edmonds–Karp algorithm](https://bliptext.com/articles/edmonds-karp-algorithm).\nSpecific variants of the algorithms achieve even lower time complexities.\nThe variant based on the highest label node selection rule has\nO(V2√E)\ntime complexity and is generally regarded as the benchmark for maximum flow algorithms.\nSubcubic\nO(VElog(V2/E))\ntime complexity can be achieved using [dynamic trees](https://bliptext.com/articles/link-cut-tree), although in practice it is less efficient.\nThe push–relabel algorithm has been extended to compute [minimum cost flows](https://bliptext.com/articles/minimum-cost-flow).\nThe 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.\n\n# History\nThe concept of a preflow was originally designed by [Alexander V. Karzanov](https://bliptext.com/articles/alexander-v-karzanov) and was published in 1974 in Soviet Mathematical Dokladi 15.\nThis 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.\nThe push-relabel algorithm was designed by [Andrew V. Goldberg](https://bliptext.com/articles/andrew-v-goldberg) and [Robert Tarjan](https://bliptext.com/articles/robert-tarjan).\nThe 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.\nBoth papers detail a generic form of the algorithm terminating in\nO(V2E)\nalong with a\nO(V3)\nsequential implementation, a\nO(VE log(V2/E))\nimplementation using dynamic trees, and parallel/distributed implementation.\nAs explained in, Goldberg-Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and [Uzi Vishkin](https://bliptext.com/articles/uzi-vishkin).\n\n# Concepts\n\n## Definitions and notations\nLet:\nbe a network with capacity function\nc: V × V → \\mathbb{R}∞\n,\na flow network, where\ns ∈ V\nand\nt ∈ V\nare chosen source and sink vertices respectively,\nf : V × V → \\mathbb{R}\ndenote a pre-flow in F,\nxf : V → \\mathbb{R}\ndenote the excess function with respect to the flow f, defined by\n,\ncf : V × V → \\mathbb{R}∞\ndenote the residual capacity function with respect to the flow f, defined by\n,\nEf ⊂ E\nbeing the edges where\nf < c\n, and\nGf (V, Ef)\ndenote the residual network of G with respect to the flow f.\nThe 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.\nThis labeling function is denoted by\n𝓁 : V → \\mathbb{N}\n. This function must satisfy the following conditions in order to be considered valid:\n𝓁(u) ≤ 𝓁(v) + 1\nfor all\n(u, v) ∈ Ef\nV\nIn the algorithm, the label values of s and t are fixed.\n𝓁(u)\nis a lower bound of the unweighted distance from u to t in\nGf\nif t is reachable from u. If u has been disconnected from t, then\n𝓁(u) −\nis a lower bound of the unweighted distance from u to s. As a result, if a valid labeling function exists, there are no\ns-t\npaths in\nGf\nbecause no such paths can be longer than\n.\nAn arc\n(u, v) ∈ Ef\nis called **admissible** if\n. The **admissible network**\nG̃f (V, Ẽf )\nis composed of the set of arcs\ne ∈ Ef\nthat are admissible.\nThe admissible network is acyclic.\nFor a fixed flow\nf\n, a vertex\nv ∉ {s, t}\nis called **active** if it has positive excess with respect to\nf\n, i.e.,\nxf (u) > 0\n.\n\n## Operations\n\n### Initialization\nThe algorithm starts by creating a residual graph, initializing the preflow values to zero and performing a set of saturating push operations on residual arcs\n(s, v)\nexiting the source, where\nv ∈ V \\ {s}\n. Similarly, the labels are initialized such that the label at the source is the number of nodes in the graph,\nV\n, and all other nodes are given a label of zero.\nOnce the initialization is complete the algorithm repeatedly performs either the push or relabel operations against active nodes until no applicable operation can be performed.\n\n### Push\nThe push operation applies on an admissible out-arc\n(u, v)\nof an active node u in\nGf\n. It moves\nmin{xf (u), cf (u,v)}\nunits of flow from u to v.\npush(u, v):\nassert xf[u] > 0 and 𝓁[u] == 𝓁[v] + 1\nΔ = min(xf[u], c[u][v] - f[u][v])\nf[u][v] += Δ\nf[v][u] -= Δ\nxf[u] -= Δ\nxf[v] += Δ\nA push operation that causes\nf (u, v)\nto reach\nc(u, v)\nis 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**.\n\n### Relabel\nThe relabel operation applies on an active node u which is neither the source nor the sink without any admissible out-arcs in\nGf\n. It modifies\n𝓁(u)\nto be the minimum value such that an admissible out-arc is created.\nNote that this always increases\n𝓁(u)\nand never creates a steep arc, which is an arc\n(u, v)\nsuch that\ncf (u, v) > 0\n, and\n𝓁(u) > 𝓁(v) + 1\n.\nrelabel(u):\nassert xf[u] > 0 and 𝓁[u] <= 𝓁[v] for all v such that cf[u][v] > 0\n𝓁[u] = 1 + min(𝓁[v] for all v such that cf[u][v] > 0)\n\n### Effects of push and relabel\nAfter a push or relabel operation,\n𝓁\nremains a valid labeling function with respect to f.\nFor a push operation on an admissible arc\n(u, v)\n, it may add an arc\n(v, u)\nto\nEf\n, where\n(u, v)\nfrom\nEf\n, where it effectively removes the constraint\n𝓁(u) ≤ 𝓁(v) + 1\n.\nTo see that a relabel operation on node u preserves the validity of\n𝓁(u)\n, notice that this is trivially guaranteed by definition for the out-arcs of u in\nGf\n. For the in-arcs of u in\nGf\n, the increased\n𝓁(u)\ncan only satisfy the constraints less tightly, not violate them.\n\n# The generic push–relabel algorithm\nThe 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.\nThis generic version of the algorithm will terminate in\nO(V2E)\n.\nSince\nV\n,\n, and there are no paths longer than\nin\nGf\n, in order for\n𝓁(s)\nto satisfy the valid labeling condition s must be disconnected from t. At initialisation, the algorithm fulfills this requirement by creating a pre-flow f that saturates all out-arcs of s, after which\nis trivially valid for all\nv ∈ V \\ {s, t}\n. 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.\ngeneric-push-relabel(G, c, s, t):\ncreate a pre-flow f that saturates all out-arcs of s **let** 𝓁[s] = |V|\n**let** 𝓁[v] = 0 for all v ∈ V \\ {s}\n**while** there is an applicable push or relabel operation **do**\nexecute the operation\n\n## Correctness\nThe algorithm maintains the condition that\n𝓁\nis a valid labeling during its execution.\nThis can be proven true by examining the effects of the push and relabel operations on the label function\n𝓁\n. The relabel operation increases the label value by the associated minimum plus one which will always satisfy the\n𝓁(u) ≤ 𝓁(v) + 1\nconstraint.\nThe push operation can send flow from u to v if\n. This may add\n(v, u)\nto\nGf\nand may delete\n(u, v)\nfrom\nGf\n. The addition of\n(v, u)\nto\nGf\nwill not affect the valid labeling since\n. The deletion of\n(u, v)\nfrom\nGf\nremoves the corresponding constraint since the valid labeling property\n𝓁(u) ≤ 𝓁(v) + 1\nonly applies to residual arcs in\nGf\n.\nIf a preflow f and a valid labeling\n𝓁\nfor f exists then there is no augmenting path from s to t in the residual graph\nGf\n. This can be proven by contradiction based on inequalities which arise in the labeling function when supposing that an augmenting path does exist.\nIf the algorithm terminates, then all nodes in\nV \\ {s, t}\nare not active.\nThis means all\nv ∈ V \\ {s, t}\nhave no excess flow, and with no excess the preflow f obeys the flow conservation constraint and can be considered a normal flow.\nThis flow is the maximum flow according to the [max-flow min-cut theorem](https://bliptext.com/articles/max-flow-min-cut-theorem) since there is no augmenting path from s to t.\nTherefore, the algorithm will return the maximum flow upon termination.\n\n## Time complexity\nIn 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.\nThe numbers of relabel, saturating push and nonsaturating push operations are analyzed separately.\nIn the algorithm, the relabel operation can be performed at most\n(2\ntimes.\nThis is because the labeling\n𝓁(u)\nvalue for any node u can never decrease, and the maximum label value is at most\n2\nfor all nodes.\nThis means the relabel operation could potentially be performed\n2\ntimes for all nodes\nV \\ {s, t}\n(i.e.\n). This results in a bound of\nO(V2)\nfor the relabel operation.\nEach saturating push on an admissible arc\n(u, v)\nremoves the arc from\nGf\n. For the arc to be reinserted into\nGf\nfor another saturating push, v must first be relabeled, followed by a push on the arc\n(v, u)\n, then u must be relabeled.\nIn the process,\n𝓁(u)\nincreases by at least two.\nTherefore, there are\nO(V)\nsaturating pushes on\n(u, v)\n, and the total number of saturating pushes is at most\n2\n. This results in a time bound of\nO(VE)\nfor the saturating push operations.\nBounding the number of nonsaturating pushes can be achieved via a [potential argument](https://bliptext.com/articles/potential-method).\nWe use the potential function\n(i.e.\nΦ\nis the sum of the labels of all active nodes). It is obvious that\nΦ\nis\n0\ninitially and stays nonnegative throughout the execution of the algorithm.\nBoth relabels and saturating pushes can increase\nΦ\n. However, the value of\nΦ\nmust be equal to 0 at termination since there cannot be any remaining active nodes at the end of the algorithm's execution.\nThis 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\nΦ\nto terminate with a value of 0.\nThe relabel operation can increase\nΦ\nby at most\n(2\n. A saturating push on\n(u, v)\nactivates v if it was inactive before the push, increasing\nΦ\nby at most\n2\n. Hence, the total contribution of all saturating pushes operations to\nΦ\nis at most\n(2\n. A nonsaturating push on\n(u, v)\nalways deactivates u, but it can also activate v as in a saturating push.\nAs a result, it decreases\nΦ\nby at least\n𝓁(u) − 𝓁(v) = 1\n. Since relabels and saturating pushes increase\nΦ\n, the total number of nonsaturating pushes must make up the difference of\n(2\n. This results in a time bound of\nO(V2E)\nfor the nonsaturating push operations.\nIn sum, the algorithm executes\nO(V2)\nrelabels,\nO(VE)\nsaturating pushes and\nO(V2E)\nnonsaturating pushes.\nData structures can be designed to pick and execute an applicable operation in\nO(1)\ntime.\nTherefore, the time complexity of the algorithm is\nO(V2E)\n.\n\n## Example\nThe following is a sample execution of the generic push-relabel algorithm, as defined above, on the following simple network flow graph diagram.\nIn the example, the h and e values denote the label\n𝓁\nand excess\nxf\n, respectively, of the node during the execution of the algorithm.\nEach residual graph in the example only contains the residual arcs with a capacity larger than zero.\nEach residual graph may contain multiple iterations of the perform operation loop.\nThe example (but with initial flow of 0) can be run [here](https://bliptext.com/articles/undefined) interactively.\n\n# Practical implementations\nWhile the generic push–relabel algorithm has\nO(V2E)\ntime complexity, efficient implementations achieve\nO(V3)\nor lower time complexity by enforcing appropriate rules in selecting applicable push and relabel operations.\nThe empirical performance can be further improved by heuristics.\n\n## \"Current-arc\" data structure and discharge operation\nThe \"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.\nIf 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.\nBased on the \"current-arc\" data structure, the discharge operation can be defined.\nA 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.\ndischarge(u):\n**while** xf[u] > 0 **do**\n**if** current-arc[u] has run off the end of neighbors[u] **then**\nrelabel(u)\nrewind current-arc[u]\n**else**\n**let** (u, v) = current-arc[u]\n**if** (u, v) is admissible **then**\npush(u, v) **let** current-arc[u] point to the next neighbor of u Finding the next admissible edge to push on has O(1) [amortized complexity](https://bliptext.com/articles/amortized-complexity).\nThe 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 u is relabelled.\nTherefore, when the pointer runs off, there are no admissible unsaturated edges and we have to relabel the active node u, so having moved the pointer O(V) times is paid for by the O(V) relabel operation.\n\n## Active node selection rules\nDefinition of the discharge operation reduces the push–relabel algorithm to repeatedly selecting an active node to discharge.\nDepending on the selection rule, the algorithm exhibits different time complexities.\nFor the sake of brevity, we ignore s and t when referring to the nodes in the following discussion.\n\n### FIFO selection rule\nThe [FIFO](https://bliptext.com/articles/fifo-computing-and-electronics) push–relabel algorithm organizes the active nodes into a queue.\nThe initial active nodes can be inserted in arbitrary order.\nThe algorithm always removes the node at the front of the queue for discharging.\nWhenever an inactive node becomes active, it is appended to the back of the queue.\nThe algorithm has\nO(V3)\ntime complexity.\n\n### Relabel-to-front selection rule\nThe relabel-to-front push–relabel algorithm organizes all nodes into a linked list and maintains the invariant that the list is [topologically sorted](https://bliptext.com/articles/topological-sorting) with respect to the admissible network.\nThe algorithm scans the list from front to back and performs a discharge operation on the current node if it is active.\nIf the node is relabeled, it is moved to the front of the list, and the scan is restarted from the front.\nThe algorithm also has\nO(V3)\ntime complexity.\n\n### Highest label selection rule\nThe highest-label push–relabel algorithm organizes all nodes into buckets indexed by their labels.\nThe algorithm always selects an active node with the largest label to discharge.\nThe algorithm has\nO(V2√E)\ntime complexity.\nIf the lowest-label selection rule is used instead, the time complexity becomes\nO(V2E)\n.\n\n## Implementation techniques\nAlthough in the description of the generic push–relabel algorithm above,\n𝓁(u)\nis set to zero for each node u other than s and t at the beginning, it is preferable to perform a backward [breadth-first search](https://bliptext.com/articles/breadth-first-search) from t to compute exact labels.\nThe algorithm is typically separated into two phases.\nPhase one computes a maximum pre-flow by discharging only active nodes whose labels are below n. Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reach t to s. It can be shown that phase two has\nO(VE)\ntime complexity regardless of the order of push and relabel operations and is therefore dominated by phase one.\nAlternatively, it can be implemented using flow decomposition.\nHeuristics are crucial to improving the empirical performance of the algorithm.\nTwo commonly used heuristics are the gap heuristic and the global relabeling heuristic.\nThe gap heuristic detects gaps in the labeling function.\nIf there is a label 0 < 𝓁' < for which there is no node u such that\n, then any node u with\n𝓁' < 𝓁(u) <\nhas been disconnected from t and can be relabeled to\n(\nimmediately.\nThe global relabeling heuristic periodically performs backward breadth-first search from t in\nGf\nto compute the exact labels of the nodes.\nBoth heuristics skip unhelpful relabel operations, which are a bottleneck of the algorithm and contribute to the ineffectiveness of dynamic trees.\n\n# Sample implementations","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T06:54:46.608Z","updated_at":"2025-01-26T06:54:46.608Z","search_vector":"'algorithm':5 'flow':4 'maximum':3 'push':1 'relabel':2","search_content":" \n \n\n# \nIn [mathematical optimization](https://bliptext.com/articles/mathematical-optimization), the **push–relabel algorithm** (alternatively, **preflow–push algorithm**) is an algorithm for computing [maximum flows](https://bliptext.com/articles/maximum-flow) in a [flow network](https://bliptext.com/articles/flow-network).\nThe name \"push–relabel\" comes from the two basic operations used in the algorithm.\nThroughout 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.\nIn comparison, the [Ford–Fulkerson algorithm](https://bliptext.com/articles/ford-fulkerson-algorithm) performs global augmentations that send flow following paths from the source all the way to the sink.\nThe push–relabel algorithm is considered one of the most efficient maximum flow algorithms.\nThe generic algorithm has a [strongly polynomial](https://bliptext.com/articles/strongly-polynomial)\nO(V2E)\ntime complexity, which is asymptotically more efficient than the\nO(VE2)\n[Edmonds–Karp algorithm](https://bliptext.com/articles/edmonds-karp-algorithm).\nSpecific variants of the algorithms achieve even lower time complexities.\nThe variant based on the highest label node selection rule has\nO(V2√E)\ntime complexity and is generally regarded as the benchmark for maximum flow algorithms.\nSubcubic\nO(VElog(V2/E))\ntime complexity can be achieved using [dynamic trees](https://bliptext.com/articles/link-cut-tree), although in practice it is less efficient.\nThe push–relabel algorithm has been extended to compute [minimum cost flows](https://bliptext.com/articles/minimum-cost-flow).\nThe 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.\n\n# History\nThe concept of a preflow was originally designed by [Alexander V. Karzanov](https://bliptext.com/articles/alexander-v-karzanov) and was published in 1974 in Soviet Mathematical Dokladi 15.\nThis 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.\nThe push-relabel algorithm was designed by [Andrew V. Goldberg](https://bliptext.com/articles/andrew-v-goldberg) and [Robert Tarjan](https://bliptext.com/articles/robert-tarjan).\nThe 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.\nBoth papers detail a generic form of the algorithm terminating in\nO(V2E)\nalong with a\nO(V3)\nsequential implementation, a\nO(VE log(V2/E))\nimplementation using dynamic trees, and parallel/distributed implementation.\nAs explained in, Goldberg-Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and [Uzi Vishkin](https://bliptext.com/articles/uzi-vishkin).\n\n# Concepts\n\n## Definitions and notations\nLet:\nbe a network with capacity function\nc: V × V → \\mathbb{R}∞\n,\na flow network, where\ns ∈ V\nand\nt ∈ V\nare chosen source and sink vertices respectively,\nf : V × V → \\mathbb{R}\ndenote a pre-flow in F,\nxf : V → \\mathbb{R}\ndenote the excess function with respect to the flow f, defined by\n,\ncf : V × V → \\mathbb{R}∞\ndenote the residual capacity function with respect to the flow f, defined by\n,\nEf ⊂ E\nbeing the edges where\nf 0\n.\n\n## Operations\n\n### Initialization\nThe algorithm starts by creating a residual graph, initializing the preflow values to zero and performing a set of saturating push operations on residual arcs\n(s, v)\nexiting the source, where\nv ∈ V \\ {s}\n. Similarly, the labels are initialized such that the label at the source is the number of nodes in the graph,\nV\n, and all other nodes are given a label of zero.\nOnce the initialization is complete the algorithm repeatedly performs either the push or relabel operations against active nodes until no applicable operation can be performed.\n\n### Push\nThe push operation applies on an admissible out-arc\n(u, v)\nof an active node u in\nGf\n. It moves\nmin{xf (u), cf (u,v)}\nunits of flow from u to v.\npush(u, v):\nassert xf[u] > 0 and 𝓁[u] == 𝓁[v] + 1\nΔ = min(xf[u], c[u][v] - f[u][v])\nf[u][v] += Δ\nf[v][u] -= Δ\nxf[u] -= Δ\nxf[v] += Δ\nA push operation that causes\nf (u, v)\nto reach\nc(u, v)\nis 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**.\n\n### Relabel\nThe relabel operation applies on an active node u which is neither the source nor the sink without any admissible out-arcs in\nGf\n. It modifies\n𝓁(u)\nto be the minimum value such that an admissible out-arc is created.\nNote that this always increases\n𝓁(u)\nand never creates a steep arc, which is an arc\n(u, v)\nsuch that\ncf (u, v) > 0\n, and\n𝓁(u) > 𝓁(v) + 1\n.\nrelabel(u):\nassert xf[u] > 0 and 𝓁[u] 0\n𝓁[u] = 1 + min(𝓁[v] for all v such that cf[u][v] > 0)\n\n### Effects of push and relabel\nAfter a push or relabel operation,\n𝓁\nremains a valid labeling function with respect to f.\nFor a push operation on an admissible arc\n(u, v)\n, it may add an arc\n(v, u)\nto\nEf\n, where\n(u, v)\nfrom\nEf\n, where it effectively removes the constraint\n𝓁(u) ≤ 𝓁(v) + 1\n.\nTo see that a relabel operation on node u preserves the validity of\n𝓁(u)\n, notice that this is trivially guaranteed by definition for the out-arcs of u in\nGf\n. For the in-arcs of u in\nGf\n, the increased\n𝓁(u)\ncan only satisfy the constraints less tightly, not violate them.\n\n# The generic push–relabel algorithm\nThe 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.\nThis generic version of the algorithm will terminate in\nO(V2E)\n.\nSince\nV\n,\n, and there are no paths longer than\nin\nGf\n, in order for\n𝓁(s)\nto satisfy the valid labeling condition s must be disconnected from t. At initialisation, the algorithm fulfills this requirement by creating a pre-flow f that saturates all out-arcs of s, after which\nis trivially valid for all\nv ∈ V \\ {s, t}\n. 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.\ngeneric-push-relabel(G, c, s, t):\ncreate a pre-flow f that saturates all out-arcs of s **let** 𝓁[s] = |V|\n**let** 𝓁[v] = 0 for all v ∈ V \\ {s}\n**while** there is an applicable push or relabel operation **do**\nexecute the operation\n\n## Correctness\nThe algorithm maintains the condition that\n𝓁\nis a valid labeling during its execution.\nThis can be proven true by examining the effects of the push and relabel operations on the label function\n𝓁\n. The relabel operation increases the label value by the associated minimum plus one which will always satisfy the\n𝓁(u) ≤ 𝓁(v) + 1\nconstraint.\nThe push operation can send flow from u to v if\n. This may add\n(v, u)\nto\nGf\nand may delete\n(u, v)\nfrom\nGf\n. The addition of\n(v, u)\nto\nGf\nwill not affect the valid labeling since\n. The deletion of\n(u, v)\nfrom\nGf\nremoves the corresponding constraint since the valid labeling property\n𝓁(u) ≤ 𝓁(v) + 1\nonly applies to residual arcs in\nGf\n.\nIf a preflow f and a valid labeling\n𝓁\nfor f exists then there is no augmenting path from s to t in the residual graph\nGf\n. This can be proven by contradiction based on inequalities which arise in the labeling function when supposing that an augmenting path does exist.\nIf the algorithm terminates, then all nodes in\nV \\ {s, t}\nare not active.\nThis means all\nv ∈ V \\ {s, t}\nhave no excess flow, and with no excess the preflow f obeys the flow conservation constraint and can be considered a normal flow.\nThis flow is the maximum flow according to the [max-flow min-cut theorem](https://bliptext.com/articles/max-flow-min-cut-theorem) since there is no augmenting path from s to t.\nTherefore, the algorithm will return the maximum flow upon termination.\n\n## Time complexity\nIn 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.\nThe numbers of relabel, saturating push and nonsaturating push operations are analyzed separately.\nIn the algorithm, the relabel operation can be performed at most\n(2\ntimes.\nThis is because the labeling\n𝓁(u)\nvalue for any node u can never decrease, and the maximum label value is at most\n2\nfor all nodes.\nThis means the relabel operation could potentially be performed\n2\ntimes for all nodes\nV \\ {s, t}\n(i.e.\n). This results in a bound of\nO(V2)\nfor the relabel operation.\nEach saturating push on an admissible arc\n(u, v)\nremoves the arc from\nGf\n. For the arc to be reinserted into\nGf\nfor another saturating push, v must first be relabeled, followed by a push on the arc\n(v, u)\n, then u must be relabeled.\nIn the process,\n𝓁(u)\nincreases by at least two.\nTherefore, there are\nO(V)\nsaturating pushes on\n(u, v)\n, and the total number of saturating pushes is at most\n2\n. This results in a time bound of\nO(VE)\nfor the saturating push operations.\nBounding the number of nonsaturating pushes can be achieved via a [potential argument](https://bliptext.com/articles/potential-method).\nWe use the potential function\n(i.e.\nΦ\nis the sum of the labels of all active nodes). It is obvious that\nΦ\nis\n0\ninitially and stays nonnegative throughout the execution of the algorithm.\nBoth relabels and saturating pushes can increase\nΦ\n. However, the value of\nΦ\nmust be equal to 0 at termination since there cannot be any remaining active nodes at the end of the algorithm's execution.\nThis 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\nΦ\nto terminate with a value of 0.\nThe relabel operation can increase\nΦ\nby at most\n(2\n. A saturating push on\n(u, v)\nactivates v if it was inactive before the push, increasing\nΦ\nby at most\n2\n. Hence, the total contribution of all saturating pushes operations to\nΦ\nis at most\n(2\n. A nonsaturating push on\n(u, v)\nalways deactivates u, but it can also activate v as in a saturating push.\nAs a result, it decreases\nΦ\nby at least\n𝓁(u) − 𝓁(v) = 1\n. Since relabels and saturating pushes increase\nΦ\n, the total number of nonsaturating pushes must make up the difference of\n(2\n. This results in a time bound of\nO(V2E)\nfor the nonsaturating push operations.\nIn sum, the algorithm executes\nO(V2)\nrelabels,\nO(VE)\nsaturating pushes and\nO(V2E)\nnonsaturating pushes.\nData structures can be designed to pick and execute an applicable operation in\nO(1)\ntime.\nTherefore, the time complexity of the algorithm is\nO(V2E)\n.\n\n## Example\nThe following is a sample execution of the generic push-relabel algorithm, as defined above, on the following simple network flow graph diagram.\nIn the example, the h and e values denote the label\n𝓁\nand excess\nxf\n, respectively, of the node during the execution of the algorithm.\nEach residual graph in the example only contains the residual arcs with a capacity larger than zero.\nEach residual graph may contain multiple iterations of the perform operation loop.\nThe example (but with initial flow of 0) can be run [here](https://bliptext.com/articles/undefined) interactively.\n\n# Practical implementations\nWhile the generic push–relabel algorithm has\nO(V2E)\ntime complexity, efficient implementations achieve\nO(V3)\nor lower time complexity by enforcing appropriate rules in selecting applicable push and relabel operations.\nThe empirical performance can be further improved by heuristics.\n\n## \"Current-arc\" data structure and discharge operation\nThe \"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.\nIf 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.\nBased on the \"current-arc\" data structure, the discharge operation can be defined.\nA 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.\ndischarge(u):\n**while** xf[u] > 0 **do**\n**if** current-arc[u] has run off the end of neighbors[u] **then**\nrelabel(u)\nrewind current-arc[u]\n**else**\n**let** (u, v) = current-arc[u]\n**if** (u, v) is admissible **then**\npush(u, v) **let** current-arc[u] point to the next neighbor of u Finding the next admissible edge to push on has O(1) [amortized complexity](https://bliptext.com/articles/amortized-complexity).\nThe 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 u is relabelled.\nTherefore, when the pointer runs off, there are no admissible unsaturated edges and we have to relabel the active node u, so having moved the pointer O(V) times is paid for by the O(V) relabel operation.\n\n## Active node selection rules\nDefinition of the discharge operation reduces the push–relabel algorithm to repeatedly selecting an active node to discharge.\nDepending on the selection rule, the algorithm exhibits different time complexities.\nFor the sake of brevity, we ignore s and t when referring to the nodes in the following discussion.\n\n### FIFO selection rule\nThe [FIFO](https://bliptext.com/articles/fifo-computing-and-electronics) push–relabel algorithm organizes the active nodes into a queue.\nThe initial active nodes can be inserted in arbitrary order.\nThe algorithm always removes the node at the front of the queue for discharging.\nWhenever an inactive node becomes active, it is appended to the back of the queue.\nThe algorithm has\nO(V3)\ntime complexity.\n\n### Relabel-to-front selection rule\nThe relabel-to-front push–relabel algorithm organizes all nodes into a linked list and maintains the invariant that the list is [topologically sorted](https://bliptext.com/articles/topological-sorting) with respect to the admissible network.\nThe algorithm scans the list from front to back and performs a discharge operation on the current node if it is active.\nIf the node is relabeled, it is moved to the front of the list, and the scan is restarted from the front.\nThe algorithm also has\nO(V3)\ntime complexity.\n\n### Highest label selection rule\nThe highest-label push–relabel algorithm organizes all nodes into buckets indexed by their labels.\nThe algorithm always selects an active node with the largest label to discharge.\nThe algorithm has\nO(V2√E)\ntime complexity.\nIf the lowest-label selection rule is used instead, the time complexity becomes\nO(V2E)\n.\n\n## Implementation techniques\nAlthough in the description of the generic push–relabel algorithm above,\n𝓁(u)\nis set to zero for each node u other than s and t at the beginning, it is preferable to perform a backward [breadth-first search](https://bliptext.com/articles/breadth-first-search) from t to compute exact labels.\nThe algorithm is typically separated into two phases.\nPhase one computes a maximum pre-flow by discharging only active nodes whose labels are below n. Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reach t to s. It can be shown that phase two has\nO(VE)\ntime complexity regardless of the order of push and relabel operations and is therefore dominated by phase one.\nAlternatively, it can be implemented using flow decomposition.\nHeuristics are crucial to improving the empirical performance of the algorithm.\nTwo commonly used heuristics are the gap heuristic and the global relabeling heuristic.\nThe gap heuristic detects gaps in the labeling function.\nIf there is a label 0 < 𝓁' < for which there is no node u such that\n, then any node u with\n𝓁' < 𝓁(u) <\nhas been disconnected from t and can be relabeled to\n(\nimmediately.\nThe global relabeling heuristic periodically performs backward breadth-first search from t in\nGf\nto compute the exact labels of the nodes.\nBoth heuristics skip unhelpful relabel operations, which are a bottleneck of the algorithm and contribute to the ineffectiveness of dynamic trees.\n\n# Sample implementations","revisionCount":0},"hasMore":false,"nextCursor":null}