# Ford-Fulkerson Max Flow Algorithm

In this post I will step through the execution of the Ford-Fulkerson Max Flow algorithm using the Edmond-Karp Breadth First Search method. If you are learning this for the first time I suggest you watch this video tutorial, in which the same graph is used, and look at this Java source code for more implementation details.

### Ford-Fulkerson Algorithm

While there exists and augmenting path:
• Find an augmenting path
• Compute the bottleneck capacity
• Increase flow on that path by the bottleneck capacity

### Path Search: Iteration 1

##### Enqueue A and mark as visited
 A
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 0, 3) (C→A, 0, 0) – B – – (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) – D – – (A→D, 0, 3) (C→D, 0, 1) (D→E, 0, 2) (D→F, 0, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 0, 2) (E→G, 0, 1) – F – – (D→F, 0, 6) (F→G, 0, 9) – G – – (F→G, 0, 9) (E→G, 0, 1)

##### Dequeue A
 A
Find edges incident to A with destination vertices that haven’t been visited, and that have residual capacities greater than zero.

Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B A B False 3 – 0 = 3 True A→D A D False 3 – 0 = 3 True C→A A C False 0 False
residualCapacity(Vertex to) {
if (to != edge.to()) {
return edge.flow;
}
else {
return edge.capacity - edge.flow;
}

Mark vertices B and D as visited, add them to the queue, and add A as their parent, and add the edges to B and D.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True (A→B, 0, 3) (A→D, 0, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) – C – (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) A D True (A→D, 0, 3) (A→D, 0, 3) (C→D, 0, 1) (D→E, 0, 2) (D→F, 0, 6) – E – (E→B, 0, 1) (C→E, 0, 2) (D→E, 0, 2) (E→G, 0, 1) – F – (D→F, 0, 6) (F→G, 0, 9) – G – (F→G, 0, 9) (E→G, 0, 1)
##### Dequeue B
 B D
Find edges incident to B with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B B A True 0 False B→C B C False 4 – 0 = 4 True E→B B E False 0 False
Mark vertices C as visited, add it to the queue, set B as its parent, and add the edge to C.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True (A→B, 0, 3) (A→D, 0, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) A D True (A→D, 0, 3) (A→D, 0, 3) (C→D, 0, 1) (D→E, 0, 2) (D→F, 0, 6) – E – (E→B, 0, 1) (C→E, 0, 2) (D→E, 0, 2) (E→G, 0, 1) – F – (D→F, 0, 6) (F→G, 0, 9) – G – (F→G, 0, 9) (E→G, 0, 1)
##### Dequeue D
 D C
Find edges incident to D with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→D D A True 0 False C→D D C True 0 False D→E D E False 2 True D→F D F False 6 True
Mark vertices E and F as visited, add them to the Queue, set their parent to D, and add the edges.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True (A→B, 0, 3) (A→D, 0, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) A D True (A→D, 0, 3) (A→D, 0, 3) (C→D, 0, 1) (D→E, 0, 2) (D→F, 0, 6) D E True (D→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 0, 2) (E→G, 0, 1) D F True (D→F, 0, 6) (D→F, 0, 6) (F→G, 0, 9) – G – (F→G, 0, 9) (E→G, 0, 1)
##### Dequeue C
 C E F
Find edges incident to C with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False C→A C A True 3 False B→C C B True 0 False C→D C D True 1 False C→E C E True 2 False
Dequeue E
 E F
Find edges incident to E with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→B E B True 1 False C→E E C True 0 False D→E E D True 2 False E→G E G False 1 True
Mark vertices G as visited, add them to the Queue, and set their parent to G.

Data Structures

 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True (A→B, 0, 3) (A→D, 0, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) A D True (A→D, 0, 3) (A→D, 0, 3) (C→D, 0, 1) (D→E, 0, 2) (D→F, 0, 6) D E True (D→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 0, 2) (E→G, 0, 1) D F True (D→F, 0, 6) (D→F, 0, 6) (F→G, 0, 9) E G True (E→G, 0, 1) (F→G, 0, 9) (E→G, 0, 1)
##### Dequeue F
 F G
Find edges incident to F with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False D→F F D True 0 False F→G F G True 9 False
##### Dequeue G
 G
Find edges incident to G with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→G G E True 0 False F→G G F True 9 False
##### Determining the Path
We can work backwards from the sink in order to determine the path. G, E, D, A (A→D→E→G).
##### Determining the Bottleneck Capacity
Starting from the sink vertex G we work backwards to the source calculating the min residual capacity.
bottleneck = Infinity;
v = Graph.sink();
while (v != Graph.source()) {
residualCapacity = edgeTo(v).residualCapacity();
bottleneck = Math.min(edgeTo(v).residualCapacity(), bottleneck);
v = parent(v);
}

 Parent To Back Edge Capacity Flow Max Flow Bottleneck (min flow) New Flow Edge To Before Edge To After A D False 3 0 3 – 0 = 3 1 1 (A→D, 0, 3) (A→D, 1, 3) D E False 2 0 2 – 0 = 2 1 1 (D→E, 0, 2) ( (D→E, 1, 2) E G False 1 0 1-0 = 1 1 1 (E→G, 0, 1) (E→G, 1, 1)

Edge E→G: bottleneck = 1
##### Updating (Augmenting) the Path Edges
To augment the path we work backwards as we did when determining the bottleneck capacity, but this time we update the residual capacity of the edge reverence in edgeTo for each vertex on the path.
v = G.sink();
while (v != G.source()) {
v = parent[v];
}
Edge {
...
if (toVertex == from) {
flow = flow - value;
}
else {
flow = flow + value;
}
}
}

 Parent To Path Bottleneck Edge To Before Edge To After A D 1 (A→D, 0, 3) (A→D, 1, 3) D E 1 (D→E, 0, 2) ( (D→E, 1, 2) E G 1 (E→G, 0, 1) (E→G, 1, 1)
Critical Edge = E→G
Max Flow = 1

### Path Search: Iteration 2

##### Enqueue A and mark as visited
 A
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 1, 3) (C→A, 0, 0) – B – – (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) – D – – (A→D, 0, 1) (C→D, 0, 1) (D→E, 01, 2) (D→F, 0, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 0, 6) (F→G, 0, 9) – G – – (F→G, 0, 9) (E→G, 1, 1)
##### Dequeue A
 A
Find edges incident to A with destination vertices that haven’t been visited, and that have residual capacities greater than zero.

Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B A B False 3 True A→D A D False 3 – 1 = 2 True C→A A C False 0 False
Mark vertices B and D as visited, add them to the queue, and add A as their parent, and add the edges to B and D.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 1, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) A D True (A→D, 1, 3) (A→D, 0, 1) (C→D, 0, 1) (D→E, 01, 2) (D→F, 0, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 0, 6) (F→G, 0, 9) – G – – (F→G, 0, 9) (E→G, 1, 1)
##### Dequeue B
 B D
Find edges incident to B with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B B A True 0 False B→C B C False 4 True E→B B E False 0 False
Mark vertices C as visited, add it to the queue, set B as its parent, and add the edge to C.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 1, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) A D True (A→D, 1, 3) (A→D, 0, 1) (C→D, 0, 1) (D→E, 01, 2) (D→F, 0, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 0, 6) (F→G, 0, 9) – G – – (F→G, 0, 9) (E→G, 1, 1)
##### Dequeue D
 D C
Find edges incident to D with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→D D A True 1 False C→D D C True 0 False D→E D E False 1 True D→F D F False 6 True
Mark vertices E and F as visited, add them to the Queue, set their parent to D, and add the edges.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 1, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) A D True (A→D, 1, 3) (A→D, 0, 1) (C→D, 0, 1) (D→E, 01, 2) (D→F, 0, 6) D E True (D→E, 01, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) D F True (D→F, 0, 6) (D→F, 0, 6) (F→G, 0, 9) – G – – (F→G, 0, 9) (E→G, 1, 1)
##### Dequeue C
 C E F
Find edges incident to C with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False C→A C A True 3 False B→C C B True 0 False C→D C D True 2 False C→E C E True 2 False

##### Dequeue E
 E F
Find edges incident to E with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→B E B True 1 False C→E E C True 0 False D→E E D True 1 False E→G E G False 0 False

##### Dequeue F
 F
Find edges incident to F with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False D→F F D True 0 False F→G F G False 9 True
Mark vertices G as visited, add it to the Queue, set their parent to F, and add the edges.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 1, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) A D True (A→D, 1, 3) (A→D, 0, 1) (C→D, 0, 1) (D→E, 01, 2) (D→F, 0, 6) D E True (D→E, 01, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) D F True (D→F, 0, 6) (D→F, 0, 6) (F→G, 0, 9) F G True (F→G, 0, 9) (F→G, 0, 9) (E→G, 1, 1)
##### Dequeue G
 G
Find edges incident to F with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→G G E True 1 False F→G G F True 0 False
##### Determining the Path
Working backwards from G using the edgeTo array we determine the path to be A, D, F, G.
##### Determining the Bottleneck Capacity
Starting from the sink vertex G we work backwards to the source calculating the min residual capacity. The bottleneck is determined to be at edge

 Parent To Back Edge Capacity Flow Max Flow Bottleneck (min flow) New Flow Edge To Before Edge To After A D False 3 1 2 2 3 (A→D, 1, 3) (A→D, 3, 3) D F False 6 0 6 2 2 (D→F, 0, 6) ( (D→F, 2, 6) F G False 9 0 9 2 2 (F→G, 0, 9) (F→G, 2, 9)
##### Updating (Augmenting) the Path Edges
To augment the path we work backwards as we did when determining the bottleneck capacity, but this time we update the residual capacity of the edge reverence in edgeTo for each vertex on the path.
 Parent To Path Bottleneck Edge To Before Edge To After A D 2 (A→D, 1, 3) (A→D, 3, 3) D F 2 (D→F, 0, 6) (D→F, 2, 6) F G 2 (F→G, 0, 9) (F→G, 2, 9)
Critical Edge = A→D
Max Flow = 1 + 2 = 3

### Path Search: Iteration 3

##### Enqueue A and mark as visited
 A
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0 3) (A→D, 3, 3) (C→A, 0, 0) – B – – (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) – D – – (A→D, 3, 3) (C→D, 0, 1) (D→E, 01, 2) (D→F, 2, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 2, 6) (F→G, 2, 9) – G – – (F→G, 2, 9) (E→G, 1, 1)
##### Dequeue A
 A
Find edges incident to A with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B A B False 3 True A→D A D False 0 False C→A A C False 0 False
Mark vertices B as visited, add them to the queue, and add A as their parent, and add the edge to B.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) – D – – (A→D, 3, 3) (C→D, 0, 1) (D→E, 01, 2) (D→F, 2, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 2, 6) (F→G, 2, 9) – G – – (F→G, 2, 9) (E→G, 1, 1)
##### Dequeue B
 B
Find edges incident to B with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B B A True 0 False B→C B C False 4 True E→B B E False 0 False
Mark vertices C as visited, add it to the queue, set B as its parent, and add the edge to C.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) – D – – (A→D, 3, 3) (C→D, 0, 1) (D→E, 01, 2) (D→F, 2, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 2, 6) (F→G, 2, 9) – G – – (F→G, 2, 9) (E→G, 1, 1)
##### Dequeue C
 C
Find edges incident to C with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False C→A C A True 3 False B→C C B True 0 False C→D C D False 1 True C→E C E False 2 True
Mark vertices D and E as visited, add them to the queue, set C as their parent, and add the edges to D ad E.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) C D True (C→D, 0, 1) (A→D, 3, 3) (C→D, 0, 1) (D→E, 1, 2) (D→F, 2, 6) C E True (C→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 2, 6) (F→G, 2, 9) – G – – (F→G, 2, 9) (E→G, 1, 1)
##### Dequeue D
 D E
Find edges incident to D with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→D D A True 3 False C→D D C True 0 False D→E D E True 1 True D→F D F False 4 True
Mark vertices E and F as visited, add them to the Queue, set their parent to D, and add the edges.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) C D True (C→D, 0, 1) (A→D, 3, 3) (C→D, 0, 1) (D→E, 1, 2) (D→F, 2, 6) C E True (C→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) D F True (D→F, 2, 6) (D→F, 2, 6) (F→G, 2, 9) – G – – (F→G, 2, 9) (E→G, 1, 1)
##### Dequeue E
 E F
Find edges incident to E with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→B E B True 1 False C→E E C True 0 False D→E E D True 1 False E→G E G False 0 False
##### Dequeue F
 F
Find edges incident to F with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False D→F F D True 2 False F→G F G False 7 True

Mark vertices G as visited, add it to the Queue, set its parent to F, and add the edge.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 0, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 0, 3) (A→B, 0, 3) (B→C, 0, 4) (E→B, 0, 1) B C True (B→C, 0, 4) (C→A, 0, 3) (B→C, 0, 4) (C→D, 0, 1) (C→E, 0, 2) C D True (C→D, 0, 1) (A→D, 3, 3) (C→D, 0, 1) (D→E, 1, 2) (D→F, 2, 6) C E True (C→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) D F True (D→F, 2, 6) (D→F, 2, 6) (F→G, 2, 9) F G True (F→G, 2, 9) (F→G, 2, 9) (E→G, 1, 1)
##### Dequeue G
 G
Find edges incident to G with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→G G E True 0 False F→G G F True 2 False

##### Determining the Path
Working backwards from G using the edgeTo array we determine the path to be: A, B, C, D, F, G

##### Determining the Bottleneck Capacity
Starting from the sink vertex G we work backwards to the source calculating the min residual capacity. The bottleneck is determined to be at edge

 Parent To Back Edge Capacity Flow Max Flow Bottleneck (min flow) New Flow Edge To Before Edge To After A B False 3 0 3 1 1 (A→B, 0, 3) (A→B, 1, 3) B C False 4 0 4 1 1 (B→C, 0, 4) (B→C, 1, 4) C D False 1 0 1 1 1 (C→D, 0, 1) (C→D, 1, 1) D F False 6 2 4 1 3 (D→F, 2, 6) (D→F, 3, 6) F G False 9 2 7 1 3 (F→G, 2, 9) (F→G, 3, 9)
Critical Edge = C→D
Max Flow = 1 + 2 + 1 = 4

### Path Search: Iteration 4

##### Enqueue A and mark as visited
 A
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 1, 3) (A→D, 3, 3) (C→A, 0, 0) – B – – (A→B, 1, 3) (B→C, 1, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 1, 4) (C→D, 1, 1) (C→E, 0, 2) – D – – (A→D, 3, 3) (C→D, 1, 1) (D→E, 1, 2) (D→F, 3, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 3, 6) (F→G, 3, 9) – G – – (F→G, 3, 9) (E→G, 1, 1)
##### Dequeue A
 A
Find edges incident to A with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B A B False 2 True A→D A D False 0 False C→A A C False 0 False
Mark vertices B as visited, add them to the queue, and add A as their parent, and add the edge to B.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 1, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 1, 3) (A→B, 1, 3) (B→C, 1, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 1, 4) (C→D, 1, 1) (C→E, 0, 2) – D – – (A→D, 3, 3) (C→D, 1, 1) (D→E, 1, 2) (D→F, 3, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 3, 6) (F→G, 3, 9) – G – – (F→G, 3, 9) (E→G, 1, 1)
##### Dequeue B
 B
Find edges incident to B with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B B A True 1 False B→C B C False 3 True E→B B E False 0 False
Mark vertices C as visited, add it to the queue, set B as its parent, and add the edge to C.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 1, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 1, 3) (A→B, 1, 3) (B→C, 1, 4) (E→B, 0, 1) B C True (B→C, 1, 4) (C→A, 0, 3) (B→C, 1, 4) (C→D, 1, 1) (C→E, 0, 2) – D – – (A→D, 3, 3) (C→D, 1, 1) (D→E, 1, 2) (D→F, 3, 6) – E – – (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 3, 6) (F→G, 3, 9) – G – – (F→G, 3, 9) (E→G, 1, 1)
##### Dequeue C
 C
Find edges incident to C with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False C→A C A True 3 False B→C C B True 1 False C→D C D False 0 False C→E C E False 2 True

Mark vertices E as visited, add it to the queue, set C as its parent, and add the edge to E.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 1, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 1, 3) (A→B, 1, 3) (B→C, 1, 4) (E→B, 0, 1) B C True (B→C, 1, 4) (C→A, 0, 3) (B→C, 1, 4) (C→D, 1, 1) (C→E, 0, 2) – D – – (A→D, 3, 3) (C→D, 1, 1) (D→E, 1, 2) (D→F, 3, 6) C E True (C→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 3, 6) (F→G, 3, 9) – G – – (F→G, 3, 9) (E→G, 1, 1)
##### Dequeue E
 E
Find edges incident to E with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→B E B True 1 False C→E E C True 0 False D→E E D False 1 True E→G E G False 0 False

Mark vertices D as visited, add it to the queue, set E as its parent, and add the edge to D.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 1, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 1, 3) (A→B, 1, 3) (B→C, 1, 4) (E→B, 0, 1) B C True (B→C, 1, 4) (C→A, 0, 3) (B→C, 1, 4) (C→D, 1, 1) (C→E, 0, 2) E D True (D→E, 1, 2) (A→D, 3, 3) (C→D, 1, 1) (D→E, 1, 2) (D→F, 3, 6) C E True (C→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) – F – – (D→F, 3, 6) (F→G, 3, 9) – G – – (F→G, 3, 9) (E→G, 1, 1)
##### Dequeue D
 D
Find edges incident to D with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→D D A True 0 False C→D D C True 1 False D→E D E True 1 False D→F D F False 3 True
Mark vertices F as visited, add it to the Queue, set its parent to D, and add the edge.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 1, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 1, 3) (A→B, 1, 3) (B→C, 1, 4) (E→B, 0, 1) B C True (B→C, 1, 4) (C→A, 0, 3) (B→C, 1, 4) (C→D, 1, 1) (C→E, 0, 2) E D True (D→E, 1, 2) (A→D, 3, 3) (C→D, 1, 1) (D→E, 1, 2) (D→F, 3, 6) C E True (C→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) D F True (D→F, 3, 6) (D→F, 3, 6) (F→G, 3, 9) – G – – (F→G, 3, 9) (E→G, 1, 1)
##### Dequeue F
 F
Find edges incident to F with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False D→F F D True 3 False F→G F G False 6 True
Mark vertices G as visited, add it to the Queue, set its parent to F, and add the edge.
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 1, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 1, 3) (A→B, 1, 3) (B→C, 1, 4) (E→B, 0, 1) B C True (B→C, 1, 4) (C→A, 0, 3) (B→C, 1, 4) (C→D, 1, 1) (C→E, 0, 2) E D True (D→E, 1, 2) (A→D, 3, 3) (C→D, 1, 1) (D→E, 1, 2) (D→F, 3, 6) C E True (C→E, 0, 2) (E→B, 0, 1) (C→E, 0, 2) (D→E, 1, 2) (E→G, 1, 1) D F True (D→F, 3, 6) (D→F, 3, 6) (F→G, 3, 9) F G True (F→G, 3, 9) (F→G, 3, 9) (E→G, 1, 1)
##### Dequeue G
 G
Find edges incident to G with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→G G E True 1 False F→G G F True 3 False

##### Determining the Path
Working backwards from G using the edgeTo array we determine the path to be: A, B, C, E, D, F, G

##### Determining the Bottleneck Capacity
Starting from the sink vertex G we work backwards to the source calculating the min residual capacity. The bottleneck is determined to be at edge

 Parent To Back Edge Capacity Flow Max Flow Bottleneck (min flow) New Flow Edge To Before Edge To After A B False 3 1 2 1 2 (A→B, 1, 3) (A→B, 2, 3) B C False 4 1 3 1 2 (B→C, 1, 4) (B→C, 2, 4) C E False 2 0 2 1 1 (C→E, 0, 2) (C→E, 1, 2) E D True 2 1 1 1 0 (D→E, 1, 2) (D→E, 0, 2) D F False 6 3 3 1 4 (D→F, 3, 6) (D→F, 4, 6) F G False 9 3 6 1 4 (F→G, 3, 9) (F→G, 4, 9)

Critical Edge = D→E
Max Flow = 1 + 2 + 1 + 1 = 5

### Path Search: Iteration 5

##### Enqueue A and mark as visited
 A
Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 2, 3) (A→D, 3, 3) (C→A, 0, 0) – B – – (A→B, 2, 3) (B→C, 2, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 2, 4) (C→D, 1, 1) (C→E, 1, 2) – D – – (A→D, 3, 3) (C→D, 1, 1) (D→E, 0, 2) (D→F, 4, 6) – E – – (E→B, 0, 1) (C→E, 1, 2) (D→E, 0, 2) (E→G, 1, 1) – F – – (D→F, 4, 6) (F→G, 4, 9) – G – – (F→G, 4, 9) (E→G, 1, 1)
##### Dequeue A
 A
Find edges incident to A with destination vertices that haven’t been visited, and that have residual capacities greater than zero.
Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B A B False 1 True A→D A D False 0 False C→A A C False 0 False

Mark vertices B as visited, add them to the queue, and add A as their parent, and add the edge to B.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 2, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 2, 3) (A→B, 2, 3) (B→C, 2, 4) (E→B, 0, 1) – C – – (C→A, 0, 3) (B→C, 2, 4) (C→D, 1, 1) (C→E, 1, 2) – D – – (A→D, 3, 3) (C→D, 1, 1) (D→E, 0, 2) (D→F, 4, 6) – E – – (E→B, 0, 1) (C→E, 1, 2) (D→E, 0, 2) (E→G, 1, 1) – F – – (D→F, 4, 6) (F→G, 4, 9) – G – – (F→G, 4, 9) (E→G, 1, 1)
##### Dequeue B
 B
Find edges incident to B with destination vertices that haven’t been visited, and that have residual capacities greater than zero.

Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False A→B B A True 2 False B→C B C False 2 True E→B B E Flase 0 False

Mark vertices C as visited, add it to the queue, set B as its parent, and add the edge to C.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 2, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 2, 3) (A→B, 2, 3) (B→C, 2, 4) (E→B, 0, 1) B C True (B→C, 2, 4) (C→A, 0, 3) (B→C, 2, 4) (C→D, 1, 1) (C→E, 1, 2) – D – – (A→D, 3, 3) (C→D, 1, 1) (D→E, 0, 2) (D→F, 4, 6) – E – – (E→B, 0, 1) (C→E, 1, 2) (D→E, 0, 2) (E→G, 1, 1) – F – – (D→F, 4, 6) (F→G, 4, 9) – G – – (F→G, 4, 9) (E→G, 1, 1)
##### Dequeue C
 C
Find edges incident to C with destination vertices that haven’t been visited, and that have residual capacities greater than zero.

Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False C→A C A True 3 False B→C C B True 2 False C→D C D False 0 False C→E C E False 1 True

Mark vertices E as visited, add it to the queue, set C as its parent, and add the edge to E.

Data Structures
 Parent To Visited Edge To Adjacent Edges (Edge, Flow, Capacity) – A True – (A→B, 2, 3) (A→D, 3, 3) (C→A, 0, 0) A B True (A→B, 2, 3) (A→B, 2, 3) (B→C, 2, 4) (E→B, 0, 1) B C True (B→C, 2, 4) (C→A, 0, 3) (B→C, 2, 4) (C→D, 1, 1) (C→E, 1, 2) – D – – (A→D, 3, 3) (C→D, 1, 1) (D→E, 0, 2) (D→F, 4, 6) C E True (C→E, 1, 2) (E→B, 0, 1) (C→E, 1, 2) (D→E, 0, 2) (E→G, 1, 1) – F – – (D→F, 4, 6) (F→G, 4, 9) – G – – (F→G, 4, 9) (E→G, 1, 1)
##### Dequeue E
 E
Find edges incident to E with destination vertices that haven’t been visited, and that have residual capacities greater than zero.

Residual Capacity Calculations
 edge From to visited(to) residualCapacity(to) residualCapacity(to) > 0 && visited(Vertex) == False E→B E B True 1 False C→E E C True 1 False D→E E D False 0 False E→G E G False 0 False
Nothing to update.

HALT: Queue Empty

#### Max Flow Network

The algorithm halts with a calculated max flow of 5.