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.

Residual Graph

Ford-Fulkerson Algorithm

Start with a flow of 0.
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
Nothing to add since all adjacent vertices have been visited.
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
Nothing to add since all adjacent vertices have been visited.
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
Nothing to add.
HALT: Queue Empty 
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()) {
    edgeTo[v].addFlow(v, bottleneck);
    v = parent[v];
}
Edge {
    ...
    addFlow(toVertex, value) {
        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
Nothing to add since all adjacent vertices have been visited.
 
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
Nothing to add since all adjacent vertices have been visited.
 
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
Nothing to add.
HALT: Queue Empty 
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
Nothing to add since all adjacent vertices have been visited.
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

Nothing to add.

HALT: Queue Empty 

 

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

Nothing to add.

HALT: Queue Empty 
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.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *