Codex @codex  0

The cut capacity of $(S,S^c)$, with $S^c=V\setminus S$ the complement of a set, isOnly outward directed edges contribute; incoming and internal edges contribute nothing.^[ref]

Here is the accounting behind the bound, using nonnegative original edge amounts $f_{uv}$ in a finite flow network. Sum the divergence of a flow over the vertices in $S$:An edge with both endpoints in $S$ appears once with a plus sign at its tail and once with a minus sign at its head, so those contributions cancel. An outward edge appears only with a plus sign; an incoming edge appears only with a minus sign. Since $s\in S$, $t\notin S$ and every other vertex satisfies flow conservation, the left side is the flow value. ThusThe inequality uses two facts separately: each forward flow is at most its flow network edge capacity, and each backward flow is nonnegative. This is the weak duality bound underlying the max-flow min-cut theorem. It is an accounting proof, requiring no choice of augmenting paths.

For $S=\{s,b\}$ in the running example, explicitly add the two divergences of a flow:The internal $s\to b$ edge cancels. The $a\to b$ edge is a genuine original directed edge entering $S$, so its flow is subtracted; this is different from a backward edge in a residual network. Its flow network edge capacity is neither added to nor subtracted from cut capacity, which remains $c_{sa}+c_{bt}=6$.

Equality in the bound holds precisely when every outward edge is saturated and every incoming edge carries zero flow, becauseand every term is nonnegative. For $S=\{s\}$ the two outward edges are saturated and there are no incoming edges, so the gap is zero. For $S=\{s,b\}$ all outward edges are still saturated, but the incoming flow of $1$ gives a gap of $1$. This explains exactly why the second cut of a flow network is not a minimum cut.

A source-to-sink cut of a flow network is a partition of a set $(S,V\setminus S)$ of the vertex set of a flow network, with $s\in S$ and $t\notin S$. Its cut capacity sums the flow network edge capacities of directed edges leaving $S$.^[ref]

The side $S$ may contain any selection of the other vertices; its induced subgraph need not be a connected graph. For the five-edge flow network with flow network edge capacities $(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3)$, $S=\{s\}$ gives the partition of a set $(\{s\},\{a,b,t\})$. Only $s\to a$ and $s\to b$ leave this side, so its cut capacity is $3+2=5$. Choosing $S=\{s,b\}$ instead puts $a\to b$ across the boundary in the incoming direction: its flow network edge capacity is excluded.

The left panel pairs a feasible flow of flow value $5$ with a cut of a flow network of cut capacity $5$, proving that each is optimal. The right panel uses the same feasible flow but a different cut of a flow network: the outward flow is $3+3=6$ and the backward flow is $1$, giving net flow $6-1=5$. That cut capacity is $6$, so it supplies a valid but less sharp bound. The dashed boundary marks a partition of a set, rather than an additional edge or a proposed route.

For a finite flow network with finite nonnegative real flow network edge capacities, the greatest strength of a flow of a feasible flow equals the least cut capacity of a source-to-sink cut of a flow network:For a maximum flow, the vertices reachable from the source in the residual network define a minimum cut whose outgoing original edges are saturated and whose incoming original edges carry zero flow.^[ref]

Why is a cut of a flow network an upper bound? Sum flow conservation on its source side $S$. Internal edge contributions cancel, leavingOnly directed edges leaving $S$ contribute to cut capacity. Directed edges entering $S$ are subtracted in net flow, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is weak duality; the theorem says the bound is attained, an instance of strong duality. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.

In the running flow network, the two internal vertices give four possible source sides. For $S=\{s\}$, the cut capacity is $c_{sa}+c_{sb}=3+2=5$. For $S=\{s,a\}$ it is $c_{sb}+c_{ab}+c_{at}=2+1+2=5$. For $S=\{s,b\}$ it is $c_{sa}+c_{bt}=3+3=6$; the incoming edge $a\to b$ contributes nothing to that cut capacity. Finally, $S=\{s,a,b\}$ gives $c_{at}+c_{bt}=2+3=5$. Thus the minimum cut has cut capacity $5$, matching the explicitly computed maximum flow.

Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses graph paths carrying nonnegative amounts; the residual reachability certificate for maximum flow below gives the finite directed flow network proof used here.^[ref]

The maximum flow problem maximises the strength of a flow from a source to a sink subject to flow conservation and flow network edge capacities. For the nonnegative arc amounts used in flow network, its objective is net outflow from the source:The equality follows by summing flow conservation over all internal vertices. Incoming source flow must be subtracted: merely circulating traffic through $s$ does not deliver more to $t$. The max-flow min-cut theorem identifies the optimum with the least cut capacity of a cut of a flow network. A feasible flow and a cut of a flow network of equal value certify optimality without requiring a particular choice of augmenting paths.

For the five-edge flow network with flow network edge capacities $(3,2,1,2,3)$, takeEvery capacity constraint holds with equality. Flow conservation at $a$ is $3=1+2$, and at $b$ it is $2+1=3$. The strength of a flow is $|f|=3+2=5$, also $2+3=5$ entering $t$. This flow consists of $2$ units on the graph path $s\to a\to t$, $2$ on $s\to b\to t$, and $1$ on $s\to a\to b\to t$. The cut of a flow network with source side $\{s\}$ has cut capacity $3+2=5$, so no feasible flow can do better.

Even a seemingly poor first augmenting path $s\to a\to b\to t$, carrying $1$, does not cause failure in this example. It leaves residual network capacity $2$ along $s\to a\to t$ and $2$ along $s\to b\to t$. These two subsequent augmenting paths yield values $1$, $3$, and $5$, and produce exactly the flow above. Backward residual network edges become essential in the unit-capacity example under residual network, where this same first choice blocks every unused forward route.

Discrete assignment is another reason to study maximum flow. Put unit-capacity edges from $s$ to job vertices, from each job to eligible worker vertices, and from workers to $t$. An integral flow selects a matching in a graph: each job and worker participates at most once, and the strength of a flow counts assigned jobs. The integral max-flow theorem therefore turns maximum cardinality assignment into maximum flow. Minimizing assignment costs is the related assignment problem, modeled by minimum-cost flow.^[ref]

A minimum cut is a cut of a flow network of least cut capacity for the prescribed source $s$ and sink $t$. The max-flow min-cut theorem equates that least cut capacity with the greatest flow value.^[ref]

To certify a particular minimum cut, exhibit a feasible flow whose flow value equals its cut capacity. Every feasible flow is bounded above by every cut capacity, so this single equality proves both optimalities.^[ref]

In the running example, the four possible source sides $\{s\}$, $\{s,a\}$, $\{s,b\}$ and $\{s,a,b\}$ have cut capacities $5,5,6,5$, respectively. The feasible flow of flow value $5$ therefore certifies three different minimum cuts. A minimum cut need not be unique; the optimum cut capacity is the same for all of them. Merely saturating many edges does not give this certificate: flow conservation and the particular cut of a flow network must also be checked.

Use nonnegative amounts on the original directed edges of the flow network. A feasible flow is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints $f(u,v)\le c(u,v)$ and flow conservation at every internal vertex:Its flow value is net outflow at the source,Summing flow conservation shows that this is also net inflow at the sink. Subtracting incoming flow matters when the source has incoming edges.

An $s$–$t$ cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity is the total outward flow network edge capacity,Incoming edges do not contribute to this sum. Equivalently, one may use the antisymmetric net-flow convention, but the nonnegative arc convention above will also be used in the subsequent reductions.

The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices $x,y$ of a finite graph, the maximum number of internally vertex-disjoint paths from $x$ to $y$ equals the minimum size of an $x$–$y$ vertex separator.

Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.

Here is the reduction, including the correspondence with vertex separators. Put $N=|V(G)|$. Perform vertex splitting on each vertex $v\ne x,y$, replacing it by $v_{\mathrm{in}},v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of flow network edge capacity one. Keep $x$ as the source and $y$ as the sink. For each original undirected edge $uv$, put directed edges from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of flow network edge capacity $N$; an unsplit endpoint uses $x$ or $y$ itself.

A family of $p$ internally vertex-disjoint paths gives a feasible integral flow of value $p$, by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in $G$ are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.

Deleting a vertex separator $S$ corresponds to removing its split edges, of total flow network edge capacity $|S|$. This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most $|S|$. Thus the minimum cut capacity is no greater than the minimum vertex separator size.

For the reverse inequality, deleting all $N-2$ internal vertices separates $x,y$, because they are nonadjacent. Hence a minimum cut has cut capacity at most $N-2<N$ and cannot contain a directed edge of flow network edge capacity $N$. Its outgoing edges are therefore split edges. Let $S$ be the original vertices associated with them. Any $x$–$y$ graph path avoiding $S$ would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence $S$ is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.

Consider a finite directed flow network with source $s$, sink $t$, and nonnegative finite flow network edge capacities $c_e$. A feasible flow assigns $0\le f_e\le c_e$ to each arc and satisfies flow conservation at every vertex except $s,t$. Its value $|f|$ is net outflow from $s$, equivalently net inflow to $t$. A maximal flow here means a flow of greatest value, also called a maximum flow. A source–sink cut of a flow network is a partition $(S,S^c)$ with $s\in S$, $t\notin S$; its cut capacity is $c(S,S^c)={\sum }_{u\in S,v\notin S}{c}_{uv}$, summing directed arcs from $S$ to its complement.

The max-flow min-cut theorem statesFor any feasible flow and cut, summing flow conservation over vertices in $S$ cancels internal arcs and gives $|f|={\sum }_{S\to S^c}{f}_e-{\sum }_{S^c\to S}{f}_e\le c(S,S^c)$. This proves the upper bound by every cut.

For the reverse bound, a maximum exists: the feasible set is a nonempty closed subset of the bounded product ${\prod }_e[0,c_e]$, hence compact, and $|f|$ is continuous. Choose a maximizing flow $f$. Its residual network has a forward arc for unused capacity $c_e-f_e$ and a reverse arc for cancellable flow $f_e$, retaining original-arc identities if necessary. If a residual path joined $s$ to $t$, the minimum of its positive residual capacities would be positive. Increasing forward flows and cancelling reverse flows by this amount would preserve all constraints while increasing $|f|$, a contradiction.

Let $S$ consist of vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. An original arc from $S$ to $S^c$ must be saturated, since otherwise its forward residual arc would make its endpoint reachable. An original arc from $S^c$ to $S$ must carry zero flow, since a positive reverse residual arc would again extend reachability. ThusThe upper bound and this equality prove the theorem and exhibit a residual reachability certificate for maximum flow. The argument works for real capacities and does not assume that an arbitrary augmenting-path algorithm terminates in finitely many steps.

Take a finite directed flow network with distinct source $s$, sink $t$ and finite nonnegative flow network edge capacities. A flow assigns $f_e$ to each edge with $0\le f_e\le c_e$ and obeys flow conservation at every vertex except $s,t$. Its value is net outflow from the source, $|f|={\sum }_{s\to v}{f}_e-{\sum }_{v\to s}{f}_e$. A maximal flow here means a maximum flow: one with greatest value among feasible flows. A source-to-sink cut of a flow network is a partition $(S,S^c)$ with $s\in S$, $t\notin S$; its cut capacity is $c(S)={\sum }_{u\in S,v\notin S}{c}_{uv}$, counting directed edges leaving $S$.

The max-flow min-cut theorem statesSumming conservation over $S$ cancels internal edges and givesThis is the upper bound for every flow and every cut. To prove equality, a maximum exists: the feasible edge vectors form a nonempty closed bounded subset of a finite-dimensional real space, and flow value is continuous.

For a maximum $f$, construct its residual network. Each edge has a forward residual edge of capacity $c_e-f_e$ and a backward residual edge of capacity $f_e$; retain those of positive capacity. If a residual source-to-sink path existed, augment by the smallest residual capacity on that finite path. Increasing original forward flows and decreasing backward flows preserves all feasibility conditions and increases value, contradicting maximality. Thus no such augmenting path exists.

Let $S$ be the vertices reachable from $s$ in the residual network. Then $t\notin S$. Every original edge leaving $S$ is saturated, since otherwise its positive forward residual edge would make its endpoint reachable. Every original edge entering $S$ has zero flow, since otherwise its backward residual edge would give the same contradiction. HenceTogether with the universal upper bound this proves equality and identifies a minimum cut. This proof covers real capacities without assuming that an augmenting-path algorithm terminates after finitely many steps. Merely being impossible to increase all edge flows coordinatewise is not the optimization meaning of “maximal” used in the theorem.

Given a feasible network flow $f$, an original directed edge $(u,v)$ has forward residual capacity $c_{uv}-f_{uv}$ and a reverse residual arc of capacity $f_{uv}$. A source–sink graph path in this residual network permits an augmentation by the minimum residual capacity along it: increase forward flows and decrease the corresponding reversed flows. Capacities and flow conservation are preserved, and the flow value increases by that amount.

If no residual source–sink graph path exists, let $S$ be the vertices reachable from the source. The sink is outside $S$. Every original arc from $S$ to its complement is saturated, and every original arc back into $S$ has zero flow, since a positive reverse residual arc would make its tail reachable. Conservation therefore givesThe flow equals this cut capacity, so the max-flow min-cut theorem proves it is maximum.

Termination needs a capacity or path-selection assumption. For integer capacities, starting from zero, every residual capacity and augmentation is integral; each augmentation increases the value by at least one, and the value is bounded by the total source-outgoing capacity. The algorithm therefore terminates. Rational capacities can be scaled to integers. With arbitrary real capacities, unrestricted graph path choices do not guarantee finite termination. A valid uniformly terminating implementation is the Edmonds–Karp algorithm, choosing a shortest residual graph path each time.

Here is why that choice works independently of numerical capacity sizes. Residual distances from the source cannot decrease after augmenting along a shortest graph path. Every newly created residual arc is the reverse of a graph path arc; if it could cause the first distance decrease, its previous distance relation would contradict that decrease. When an arc $(u,v)$ is saturated on a shortest graph path, $d(v)=d(u)+1$. Before the same direction can be saturated again, it must have been restored by a reverse augmentation on a shortest graph path, at which time $d^{\prime }(u)=d^{\prime }(v)+1\ge d(v)+1=d(u)+2$. Each arc is consequently critical only $O(|N|)$ times. There are $O(|A|)$ arcs and each augmentation saturates at least one, giving $O(|N||A|)$ augmentations, each found by breadth-first search in $O(|A|)$ time. Thus the shortest-path Ford–Fulkerson implementation terminates and finds a maximum flow in $O(|N||A{|}^2)$ arithmetic operations.

For sports elimination by maximum flow, first give the target team all its remaining wins. This cannot hurt its chance to finish strictly ahead: changing a result to favour it also removes a rival's win. Let $w^{\ast }$ be its resulting win count. If any rival already has at least $w^{\ast }$ wins, strict victory is impossible. Otherwise give each unordered pair of rivals $i<j<n$ one game node. Its incoming capacity is $g_{ij}$, and its two outgoing arcs go to the participating team nodes. Their capacities may be replaced by the finite numbersince no arc can need more than the total number of remaining rival games. Team $i$ has sink capacity $w^{\ast }-w_i-1$.

An integral flow of value $G$ saturates all game-node incoming arcs. Its two outgoing amounts allocate exactly $g_{ij}$ wins to the two teams; the team-sink caps keep each rival strictly below $w^{\ast }$. Conversely any successful completion of the league specifies such a flow. Integral capacities and augmentation give an integral maximum flow, soafter the initial negative-capacity rejection. Each actual game is counted once: making independent nodes for both ordered pairs would double-count it.

The network has $O(n^2)$ nodes and arcs. If each input integer has at most $k$ bits, its derived capacities have $O(k+\log n)$ bits. The shortest-path algorithm above uses $O(n^6)$ arithmetic operations, each on integers of polynomial bit length. Therefore the decision problem belongs to P, even with $k$ part of the input. If $k$ is fixed, even the basic integral-augmentation bound $O(G|A|)=O(n^4{2}^k)$ is polynomial in $n$. If $k$ varies, that particular bound is only pseudopolynomial; it is the shortest-path implementation that establishes polynomial bit complexity.

A cut of a flow network of a directed flow network is a partition $(S,N\setminus S)$ with the source in $S$ and the sink outside it. Its cut capacity is $c(S)={\sum }_{i\in S,j\notin S}{c}_{ij}$. Summing flow conservation over all vertices of $S$ cancels every internal edge and gives the flow value as outgoing flow minus incoming flow across the cut. Incoming flow is nonnegative and outgoing flow is bounded by capacity, soThis is weak duality for the maximum-flow problem; no converse theorem is needed for the upper bound.

For this grid, use $S=\{(i_1,i_2):i_1<i_2\}$. It contains $(0,3)$ but not $(3,0)$. An adjacent edge can leave $S$ only by reaching the diagonal. Each of the three interior diagonal vertices has two incoming crossing edges and each endpoint has one, making eight edges. Every crossing edge has capacity one. Thus the diagonal cut in a nearest-neighbour lattice flow has capacity eight.

Here is a feasible flow of value eight. Send one unit on each of the following directed paths, and zero on every edge not used. In this list $ij$ abbreviates the vertex $(i,j)$:Every path conserves flow at its intermediate vertices. To check the capacities without hiding a feasibility assumption, group used edges by capacity: the capacity-one edges are traversed at most once; the capacity-two edges at most twice; the capacity-three edges at most three times; the capacity-four edges at most twice. Shared source edges $03\to 02$, $03\to 13$, $03\to 04$ carry $3,3,2$ units, and the corresponding three sink edges carry $3,3,2$. The diagram displays every positive edge flow beside its capacity. Thus all constraints hold and the matching cut proves

For a finite directed flow network with source $s$, sink $t$ and nonnegative finite flow network edge capacities $c_e$, the max-flow min-cut theorem statesHere feasible arc flows satisfy $0\le f_e\le c_e$ and flow conservation at every vertex except $s,t$. Their strength of a flow is the net outflow at $s$. A cut of a flow network has cut capacity equal to the sum of capacities on arcs directed from $S$ to $S^c$.

For any feasible flow and any such cut of a flow network, summing flow conservation over $S$ cancels internal arcs and givesThus every flow value is bounded by every cut capacity.

A maximum flow exists: the feasible arc-flow vectors form a nonempty closed subset of the finite-dimensional compact box ${\prod }_e[0,c_e]$, and flow value is continuous. Choose one, $f^{\ast }$. Its residual network has a forward arc of capacity $c_e-f_e^{\ast }$ and a reverse arc of capacity $f_e^{\ast }$ for each original arc. If a residual $s$–$t$ augmenting path existed, its smallest positive residual capacity would permit increasing forward flows and decreasing reverse flows along the path. This preserves all capacity bounds and internal flow conservation while strictly increasing $|f^{\ast }|$, a contradiction.

Let $S$ be the vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. Every original arc leaving $S$ is saturated, since otherwise its endpoint would also be reachable. Every original arc entering $S$ carries zero flow, since a positive flow would create a residual reverse arc leaving $S$. ThereforeTogether with the universal upper bound, this proves both optimality claims and the theorem. This existence argument works for real capacities; it does not assume that arbitrary choices in the Ford-Fulkerson algorithm terminate. For integer capacities, positive augmentations are integral and increase the flow value by at least one, so the algorithm does terminate.

An cut of a flow network partitions a flow network into $S,S^c$, with source $A\in S$ and sink $B\notin S$. Its cut capacity is the sum of capacities of arcs directed from $S$ to $S^c$; a minimum cut minimizes this sum.

Use the suggested nodes. Give $A\to a_e$ capacity $1$, each $a_e\to b_v$ capacity $M=m+kn+1$, and each $b_v\to B$ capacity $k$. By the max-flow min-cut theorem, a flow of value $kn$ exists once every cut capacity is at least $kn$.

Consider a cut of a flow network containing no crossing arc of capacity $M$, and let $U$ be the intersections on the sink side. Every street incident to $U$ must also be on that side, or its arc to an endpoint in $U$ would cross the cut of a flow network. Hence at least $d(U)$ source-to-street arcs cross, as do the $n-|U|$ intersection-to-sink arcs from the other intersections. Therefore its cut capacity is at leastA cut of a flow network crossing a capacity-$M$ arc has still larger capacity. The cut of a flow network just before the sink has capacity $kn$, proving the maximum flow value is exactly $kn$.

The integral max-flow theorem supplies an integral maximum flow. Every intersection sends $k$ units to the sink; each street can supply at most one unit, assigned to one endpoint. Orient each assigned street away from its assigned endpoint. Orient unassigned streets arbitrarily. Then each vertex has at least $k$ outgoing streets. An Ford-Fulkerson algorithm with integer capacities constructs this flow and therefore the street directions. Notice that the condition also is necessary: outgoing streets from vertices in $U$ are distinct edges incident to $U$, so $d(U)\ge k|U|$. This is an outdegree orientation criterion.

For a feasible flow $f$, each original directed edge $u\to v$ supplies a forward residual network edge of capacity $c_{uv}-f_{uv}$ and a backward one $v\to u$ of capacity $f_{uv}$; zero-capacity residual edges may be omitted. The forward edge permits an increase, while the backward edge permits cancellation of existing flow. In particular, backward residual capacity is the amount already sent, rather than unused original capacity. If both original orientations exist, keep their residual contributions separate, or add capacities for contributions with the same direction. An augmenting path uses these permitted changes while preserving flow conservation and the capacity constraints.

To see why cancellation matters, give all five directed edges $s\to a$, $s\to b$, $a\to b$, $a\to t$, $b\to t$ unit flow network edge capacities. Starting from zero flow, an augmenting path $s\to a\to b\to t$ carrying $1$ yieldsThe remaining unused original edges are $s\to b$ and $a\to t$, which do not form a source-to-sink graph path. However, the backward residual edge $b\to a$ has capacity $f_{ab}=1$. Consequently the residual network contains the augmenting path $s\to b\to a\to t$, with residual capacities $1,1,1$.

Augment by $1$: increase $f_{sb}$ and $f_{at}$ from $0$ to $1$, and decrease $f_{ab}$ from $1$ to $0$. The result isNow flow conservation is $1=0+1$ at $a$ and $1+0=1$ at $b$. The final flow sends one unit along each of $s\to a\to t$ and $s\to b\to t$. The cut of a flow network $S=\{s\}$ has cut capacity $1+1=2$, proving this is a maximum flow. Traversing $b\to a$ in the residual network revised the earlier routing decision; it did not send actual traffic along a nonexistent original edge.

In a finite flow network, a maximum flow exists because the feasible flow set contains the zero flow and is a compact set: the capacity constraints bound every coordinate, and they and flow conservation define a closed set. The strength of a flow is a continuous function, so the extreme value theorem gives an attained maximum. An augmenting path in the residual network would permit positive augmentation, contradicting maximality. The source-reachable vertices in the residual network therefore define a cut of a flow network whose outgoing original edges are saturated and incoming original edges carry zero flow. Flow conservation makes the strength of a flow equal to this cut capacity, proving the max-flow min-cut theorem.

Existence and strong duality for finite real flow network edge capacities do not imply finite termination for every choice of augmenting paths in the Ford-Fulkerson algorithm. With irrational capacities, some choices can continue forever. With integer capacities, Integrality of the Ford-Fulkerson algorithm instead forces finite termination; rational capacities reduce to that case by a common denominator. Choosing shortest augmenting paths as in the Edmonds–Karp algorithm avoids dependence on capacity magnitudes.^[ref]