Максимальный поток (Эдмондс-Карп)

1function edmondsKarp(edges: Edge[], s: string, t: string): number {
2  // остаточные пропускные способности
3  const cap = new Map<string, number>()
4  for (const e of edges) {
5    cap.set(e.from + ':' + e.to, e.weight)
6    cap.set(e.to + ':' + e.from, cap.get(e.to + ':' + e.from) ?? 0)
7  }
8 
9  let flow = 0
10  for (;;) {
11    // BFS ищет кратчайший увеличивающий путь
12    const parent = new Map<string, string>()
13    const queue = [s]
14    const seen = new Set([s])
15    while (queue.length > 0 && !parent.has(t)) {
16      const v = queue.shift()!
17      for (const w of neighbors(v)) {
18        if (!seen.has(w) && (cap.get(v + ':' + w) ?? 0) > 0) {
19          seen.add(w)
20          parent.set(w, v)
21          queue.push(w)
22        }
23      }
24    }
25    if (!parent.has(t)) return flow // пути нет — поток максимальный
26 
27    // узкое место пути
28    let bottleneck = Infinity
29    for (let v = t; v !== s; v = parent.get(v)!) {
30      bottleneck = Math.min(bottleneck, cap.get(parent.get(v)! + ':' + v)!)
31    }
32    for (let v = t; v !== s; v = parent.get(v)!) {
33      cap.set(parent.get(v)! + ':' + v, cap.get(parent.get(v)! + ':' + v)! - bottleneck)
34      cap.set(v + ':' + parent.get(v)!, cap.get(v + ':' + parent.get(v)!)! + bottleneck)
35    }
36    flow += bottleneck
37  }
38}