# Ford-Fulkerson

### From Progteam

The **Ford Fulkerson Algorithm** is a procedure for solving the Max Flow (and therefore, also the min-cut) problem.

## Implementation

This is pretty general purpose. Operates on an adj matrix with double values. Also contains a pretty general BFS.

public static double maxFlow(double[][] capacity, int source, int sink) { double[][] residual = new double[capacity.length][capacity.length]; double maxFlow = 0; for (int i = 0; i < residual.length; i++) { for (int j = 0; j < residual.length; j++) { residual[i][j] = capacity[i][j]; } } // While there exists an augmenting path, // increment the flow along this path. int[] pred = bfs(residual, source); while (pred[sink] != -1) { // Determine the amount by which we can increment the flow. double increment = Double.POSITIVE_INFINITY; for (int u = sink; pred[u] != -2; u = pred[u]) { increment = Math.min(increment, residual[pred[u]][u]); } for (int u = sink; pred[u] != -2; u = pred[u]) { residual[pred[u]][u] -= increment; residual[u][pred[u]] += increment; } maxFlow += increment; pred = bfs(residual, source); } return maxFlow; } public static int[] bfs (double[][] graph, int start) { Queue<Integer> q = new LinkedList<Integer>(); int[] pred = new int[graph.length]; for (int i = 0; i < pred.length; i++) pred[i] = -1; q.add(start); pred[start] = -2; while (!q.isEmpty()) { int u = q.remove(); for (int v = 0; v < graph.length; v++) { if (pred[v] == -1 && graph[u][v] > 0) { q.add(v); pred[v] = u; } } } return pred; }