1function edmondsKarp(cap, s, t) {
2 const n = cap.length;
3 const flow = cap.map(r => r.map(() => 0));
4 let maxFlow = 0;
5 while (true) {
6 const parent = new Array(n).fill(-1);
7 parent[s] = s;
8 const queue = [s];
9 for (let qi = 0; qi < queue.length; qi++) {
10 const u = queue[qi];
11 for (let v = 0; v < n; v++)
12 if (parent[v] < 0 && cap[u][v] - flow[u][v] > 0) {
13 parent[v] = u;
14 queue.push(v);
15 }
16 }
17 if (parent[t] < 0) break;
18 let bottleneck = Infinity;
19 for (let v = t; v !== s; v = parent[v])
20 bottleneck = Math.min(bottleneck, cap[parent[v]][v] - flow[parent[v]][v]);
21 for (let v = t; v !== s; v = parent[v]) {
22 flow[parent[v]][v] += bottleneck;
23 flow[v][parent[v]] -= bottleneck;
24 }
25 maxFlow += bottleneck;
26 }
27 return maxFlow;
28}