演算法

1// Returns the maximum flow and the source side of a minimum cut.
2function edmondsKarp(cap: number[][], s: number, t: number): { flow: number; cut: number[] } {
3  const n = cap.length;
4  const flow = cap.map((row) => row.map(() => 0));
5  let total = 0;
6  for (;;) {
7    const parent = new Array(n).fill(-1);
8    parent[s] = s;
9    const queue = [s];
10    while (queue.length && parent[t] === -1) {
11      const u = queue.shift()!;
12      for (let v = 0; v < n; v++) {
13        if (parent[v] === -1 && cap[u][v] - flow[u][v] > 0) {
14          parent[v] = u;
15          if (v === t) break;
16          queue.push(v);
17        }
18      }
19    }
20    if (parent[t] === -1) {
21      // No path left: what is still reachable is the source side of a minimum cut.
22      const cut = parent.flatMap((p, v) => (p === -1 ? [] : [v]));
23      return { flow: total, cut };
24    }
25    let bottleneck = Infinity;
26    for (let v = t; v !== s; v = parent[v])
27      bottleneck = Math.min(bottleneck, cap[parent[v]][v] - flow[parent[v]][v]);
28    for (let v = t; v !== s; v = parent[v]) {
29      flow[parent[v]][v] += bottleneck;
30      flow[v][parent[v]] -= bottleneck;
31    }
32    total += bottleneck;
33  }
34}