Maximum flow. Ford-Fulkerson alogithm in O(V^2 * FLOW)

public class MaxFlowFordFulkerson {

  public static int maxFlow(int[][] cap, int s, int t) {
    for (int flow = 0;;) {
      int df = findPath(cap, new boolean[cap.length], s, t, Integer.MAX_VALUE);
      if (df == 0)
        return flow;
      flow += df;
    }
  }

  static int findPath(int[][] cap, boolean[] vis, int u, int t, int f) {
    if (u == t)
      return f;
    vis[utrue;
    for (int v = 0; v < vis.length; v++)
      if (!vis[v&& cap[u][v0) {
        int df = findPath(cap, vis, v, t, Math.min(f, cap[u][v]));
        if (df > 0) {
          cap[u][v-= df;
          cap[v][u+= df;
          return df;
        }
      }
    return 0;
  }

  // Usage example
  public static void main(String[] args) {
    int[][] capacity = { { 03}00}00} };
    System.out.println(== maxFlow(capacity, 02));
  }
}
Comments