Editing Ford–Fulkerson algorithm (section)

==Algorithm==
Let <math>G(V,E)</math> be a graph, and for each edge from {{mvar|u}} to {{mvar|v}}, let <math>c(u,v)</math> be the capacity and <math>f(u,v)</math> be the flow. We want to find the maximum flow from the source {{mvar|s}} to the sink {{mvar|t}}. After every step in the algorithm the following is maintained:

:{| class="wikitable"
! {{rh}} | Capacity constraints
| <math>\forall (u, v) \in E: \ f(u,v) \le c(u,v)</math> || The flow along an edge cannot exceed its capacity.
|-
! {{rh}} | Skew symmetry
| <math>\forall (u, v) \in E: \ f(u,v) = - f(v,u)</math> || The net flow from {{mvar|u}} to {{mvar|v}} must be the opposite of the net flow from {{mvar|v}} to {{mvar|u}} (see example).
|-
! {{rh}} | Flow conservation 
| <math style="vertical-align:-125%;">\forall u \in V: u \neq s \text{ and } u \neq t \Rightarrow \sum_{w \in V} f(u,w) = 0</math> || The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.
|-
! {{rh}} | Value(f)
| <math>\sum_{(s,u) \in E} f(s, u) = \sum_{(v,t) \in E} f(v, t)</math> || The flow leaving from {{mvar|s}} must be equal to the flow arriving at {{mvar|t}}.
|-
|}

This means that the flow through the network is a ''legal flow'' after each round in the algorithm. We define the '''residual network''' <math>G_f(V,E_f)</math> to be the network with capacity <math>c_f(u,v) = c(u,v) - f(u,v)</math> and no flow. Notice that it can happen that a flow from {{mvar|v}} to {{mvar|u}} is allowed in the residual
network, though disallowed in the original network: if <math>f(u,v)>0</math> and <math>c(v,u)=0</math> then <math>c_f(v,u)=c(v,u)-f(v,u)=f(u,v)>0</math>.

{{Algorithm-begin|name=Ford&ndash;Fulkerson}}
:'''Inputs'''  Given a Network <math>G = (V,E)</math> with flow capacity {{mvar|c}}, a source node {{mvar|s}}, and a sink node {{mvar|t}}
:'''Output''' Compute a flow {{mvar|f}} from {{mvar|s}} to {{mvar|t}} of maximum value
:# <math>f(u,v) \leftarrow 0</math> for all edges <math>(u,v)</math>
:# While there is a path {{mvar|p}} from {{mvar|s}} to {{mvar|t}} in <math>G_f</math>, such that <math>c_f(u,v) > 0</math> for all edges <math>(u,v) \in p</math>:
:## Find <math>c_f(p) = \min\{c_f(u,v) : (u,v) \in p\}</math>
:## For each edge <math>(u,v) \in p</math>
:### <math>f(u,v) \leftarrow f(u,v) + c_f(p)</math> (''Send flow along the path'')
:### <math>f(v,u) \leftarrow f(v,u) - c_f(p)</math> (''The flow might be "returned" later'')
{{Algorithm-end}}

The path in step 2 can be found with, for example, [[breadth-first search]] (BFS) or [[depth-first search]] in <math>G_f(V,E_f)</math>. The former is known as the [[Edmonds–Karp algorithm]].

When no more paths in step 2 can be found, {{mvar|s}} will not be able to reach {{mvar|t}} in the residual
network. If {{mvar|S}} is the set of nodes reachable by {{mvar|s}} in the residual network, then the total
capacity in the original network of edges from {{mvar|S}} to the remainder of {{mvar|V}} is on the one hand
equal to the total flow we found from {{mvar|s}} to {{mvar|t}},
and on the other hand serves as an upper bound for all such flows.
This proves that the flow we found is maximal. See also [[Max-flow min-cut theorem|Max-flow Min-cut theorem]].

If the graph <math>G(V,E)</math> has multiple sources and sinks, we act as follows:
Suppose that <math>T=\{t\mid t \text{ is a sink}\}</math> and <math>S=\{s\mid s \text{ is a source}\}</math>. Add a new source <math> s^*</math> with an edge <math>(s^*,s)</math> from <math>s^* </math> to every node <math> s\in S </math>, with capacity <math>c(s^*,s)=d_s=\sum_{(s,u)\in E}c(s,u)</math>. And add a new sink <math> t^*</math> with an edge <math>(t, t^*)</math> from every node <math> t\in T </math> to <math>t^* </math>, with capacity <math>c(t, t^*)=d_t=\sum_{(v,t)\in E}c(v,t)</math>. Then apply the Ford&ndash;Fulkerson algorithm.


Also, if a node {{mvar|u}} has capacity constraint <math>d_u</math>, we replace this node with two nodes <math>u_{\mathrm{in}},u_{\mathrm{out}}</math>, and an edge <math> (u_{\mathrm{in}},u_{\mathrm{out}}) </math>, with capacity <math>c(u_{\mathrm{in}},u_{\mathrm{out}})=d_u</math>. Then apply the Ford&ndash;Fulkerson algorithm.