Editing Ford–Fulkerson algorithm (section)

==Integer flow example==

The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source <math>A</math> and sink <math>D</math>. This example shows the worst-case behaviour of the algorithm. In each step, only a flow of <math>1</math> is sent across the network. If breadth-first-search were used instead, only two steps would be needed.

{| class="wikitable"
|- style="text-align:center"
! Step
! Flow network
|-
|Initial flow network.
| [[Image:Ford-Fulkerson example 0.svg|300px]]
|-
| Flow is sent along the augmenting path <math>A,B,C,D</math>. Here, the bottleneck is the <math>B</math>–<math>C</math> edge, so only one unit of flow is possible. 
| [[Image:Ford-Fulkerson example 1.svg|300px]]
|-
| Here, one unit of flow is sent along the augmenting path <math>A,C,B,D</math>. In this case, flow is "pushed back" from <math>C</math> to <math>B</math>. The flow into <math>C</math> that originally came from <math>B</math> now comes from <math>A</math>, and <math>B</math> is now free to send flow to <math>D</math> directly. As a result, the <math>B</math>–<math>C</math> edge is left with zero flow, but the overall flow increases by one.
| [[Image:Ford-Fulkerson example 2.svg|300px]]
|-
| colspan="2" |1998 intermediate steps are omitted here.
|-
|The final flow network, with a total flow of 2000 units.
| [[Image:Ford-Fulkerson example final.svg|300px]]
|}