Problem

Given a directed graph (flow network) with edge capacities, find the maximum possible flow from a source node to a sink node. Additionally, show how the maximum flow algorithm can be used to solve the bipartite matching problem.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Input:
# Adjacency list for the graph below (Python format):
adj = [
  [(1,3), (4,10)],    
  [(2,7), (3,10)],    
  [(6,1)],            
  [(5,3)],            
  [(5,5)],            
  [(6,4)],            
  []                  
]
s = 0
t = 6

Graph as shown below (nodes 0 to 6, with edge capacities):

mermaid diagram (see below)

Source: 0, Sink: 6
Output:
Maximum flow = 5
Explanation:
The maximum flow from node 0 to node 6 is 5, as determined by the minimum cut in the network.

graph TD;
  A("src: 0") -->|3| B(1)
  A -->|10| E(4)
  B -->|7| C(2)
  B -->|10| D(3)
  D -->|3| F(5)
  E -->|5| F
  C -->|1| G("sink: 6")
  F -->|4| G
Similar Problems

Solution

Method 1 – Edmonds-Karp Algorithm for Maximum Flow

Intuition

The Edmonds-Karp algorithm is a classic approach to compute the maximum flow in a network. It repeatedly finds the shortest augmenting path (in terms of number of edges) from source to sink using BFS, and augments flow along this path until no more augmenting paths exist.

Approach

  1. Initialize all flows to zero.
  2. While there exists an augmenting path from source to sink (found via BFS):
    • Find the minimum residual capacity along the path.
    • Augment the flow along the path by this minimum value.
    • Update the residual capacities of the edges and reverse edges.
  3. Repeat until no more augmenting paths can be found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
  int maxFlow(int n, vector<vector<pair<int,int>>>& adj, int s, int t) {
    vector<vector<int>> cap(n, vector<int>(n, 0)), flow(n, vector<int>(n, 0));
    for (int u = 0; u < n; ++u) for (auto& [v, c] : adj[u]) cap[u][v] = c;
    int ans = 0;
    while (true) {
      vector<int> par(n, -1); queue<int> q; q.push(s);
      while (!q.empty() && par[t] == -1) {
        int u = q.front(); q.pop();
        for (int v = 0; v < n; ++v) {
          if (par[v] == -1 && cap[u][v] - flow[u][v] > 0) {
            par[v] = u; q.push(v);
          }
        }
      }
      if (par[t] == -1) break;
      int f = 1e9;
      for (int v = t; v != s; v = par[v]) f = min(f, cap[par[v]][v] - flow[par[v]][v]);
      for (int v = t; v != s; v = par[v]) {
        flow[par[v]][v] += f; flow[v][par[v]] -= f;
      }
      ans += f;
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
  public int maxFlow(int n, List<List<int[]>> adj, int s, int t) {
    int[][] cap = new int[n][n], flow = new int[n][n];
    for (int u = 0; u < n; ++u)
      for (int[] e : adj.get(u)) cap[u][e[0]] = e[1];
    int ans = 0;
    while (true) {
      int[] par = new int[n]; Arrays.fill(par, -1);
      Queue<Integer> q = new LinkedList<>(); q.add(s);
      while (!q.isEmpty() && par[t] == -1) {
        int u = q.poll();
        for (int v = 0; v < n; ++v) {
          if (par[v] == -1 && cap[u][v] - flow[u][v] > 0) {
            par[v] = u; q.add(v);
          }
        }
      }
      if (par[t] == -1) break;
      int f = Integer.MAX_VALUE;
      for (int v = t; v != s; v = par[v]) f = Math.min(f, cap[par[v]][v] - flow[par[v]][v]);
      for (int v = t; v != s; v = par[v]) {
        flow[par[v]][v] += f; flow[v][par[v]] -= f;
      }
      ans += f;
    }
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def max_flow(self, n: int, adj: list[list[tuple[int,int]]], s: int, t: int) -> int:
        cap = [[0]*n for _ in range(n)]
        flow = [[0]*n for _ in range(n)]
        for u in range(n):
            for v, c in adj[u]:
                cap[u][v] = c
        ans = 0
        while True:
            par = [-1]*n
            q = [s]
            for u in q:
                for v in range(n):
                    if par[v] == -1 and cap[u][v] - flow[u][v] > 0:
                        par[v] = u
                        q.append(v)
            if par[t] == -1:
                break
            f = float('inf')
            v = t
            while v != s:
                f = min(f, cap[par[v]][v] - flow[par[v]][v])
                v = par[v]
            v = t
            while v != s:
                flow[par[v]][v] += f
                flow[v][par[v]] -= f
                v = par[v]
            ans += f
        return ans

Complexity

  • ⏰ Time complexity: O(V^2 * E), where V is the number of vertices and E is the number of edges. Each BFS takes O(E), and there can be O(V*E) augmentations.
  • 🧺 Space complexity: O(V^2), for the capacity and flow matrices.