# Ford-Fulkerson

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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) {

int[] pred = new int[graph.length];
for (int i = 0; i < pred.length; i++)
pred[i] = -1;

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) {