# 1. Introduction

The *Ford-Fulkerson Algorithm* is a method used to find the maximum flow in a flow network. It works by augmenting paths in the residual graph until no more augmenting paths can be found. The algorithm was developed by L.R. Ford Jr. and D.R. Fulkerson in 1956 and is a greedy approach to solve the max-flow min-cut problem.

# 2. Program Steps

1. Start with an initial flow as 0.

2. While there’s an augmenting path from source to sink in the residual graph:

a. Find the residual capacities along the path.

b. Find the bottleneck capacity (minimum residual capacity along the path).

c. Augment this bottleneck capacity in the original flow.

d. Update the residual graph.

3. Return the augmented flow as the maximum flow.

# 3. Code Program

```
import java.util.LinkedList;
public class FordFulkerson {
static final int V = 6; // Number of vertices in the graph
// Returns true if there's a path from source 's' to sink 't' in the residual graph.
boolean bfs(int[][] rGraph, int s, int t, int[] parent) {
boolean[] visited = new boolean[V];
for (int i = 0; i < V; ++i)
visited[i] = false;
LinkedList<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = true;
parent[s] = -1;
while (queue.size() != 0) {
int u = queue.poll();
for (int v = 0; v < V; v++) {
if (!visited[v] && rGraph[u][v] > 0) {
queue.add(v);
parent[v] = u;
visited[v] = true;
}
}
}
return visited[t];
}
// Using BFS as a searching algorithm, this method returns the maximum flow from 's' to 't'.
int fordFulkerson(int[][] graph, int s, int t) {
int u, v;
int[][] rGraph = new int[V][V];
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int[] parent = new int[V];
int maxFlow = 0;
while (bfs(rGraph, s, t, parent)) {
int pathFlow = Integer.MAX_VALUE;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
pathFlow = Math.min(pathFlow, rGraph[u][v]);
}
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= pathFlow;
rGraph[v][u] += pathFlow;
}
maxFlow += pathFlow;
}
return maxFlow;
}
public static void main(String[] args) {
int[][] graph = {
{0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
FordFulkerson m = new FordFulkerson();
System.out.println("The maximum possible flow is " + m.fordFulkerson(graph, 0, 5));
}
}
```

### Output:

The maximum possible flow is 23

# 4. Step By Step Explanation

1. The *Ford-Fulkerson* algorithm is used to determine the max-flow in a network.

2. The algorithm maintains a residual graph with capacities that can still be used.

3. The *bfs* function tries to find an augmenting path from the source to the sink.

4. Every time an augmenting path is found, the flow is incremented by the bottleneck value of that path.

5. The algorithm terminates when no more augmenting paths can be found in the residual graph.

6. The output shows the maximum flow value of the given graph, which in this case is *23*.

Note: The time complexity of the Ford-Fulkerson algorithm is dependent on how augmenting paths are chosen, and it might not always terminate for graphs with irrational capacities. The given implementation, which uses BFS, guarantees termination for integer capacities.