Maximální tok

O(V·E²)

Toková síť má zdroj, spotřebič a orientované hrany, každou s kapacitou — představ si trubky různé šířky. Maximální tok se ptá, kolik může najednou projít ze zdroje do spotřebiče, aniž by se překročila jakákoli trubka. Edmonds-Karp (BFS verze Forda-Fulkersona) opakovaně najde nejkratší zlepšující cestu — trasu zdroj→spotřebič, která má v reziduálním grafu ještě volnou kapacitu — a protlačí tolik toku, kolik dovolí její nejužší hrana. Klíčově přidává i zpětnou kapacitu, takže pozdější cesta může zrušit dřívější tok, pokud to uvolní lepší trasu. Skončí, když žádná zlepšující cesta nezbývá, a podle věty o maximálním toku a minimálním řezu se celek pak rovná nejlevnější množině trubek, která by po přeříznutí oddělila zdroj od spotřebiče. Každá hrana ukazuje tok/kapacitu; tlačená cesta je zvýrazněna. BFS ho omezuje na O(V·E²).

Orientovaný graf
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Začni s nulovým tokem; každá hrana ukazuje 0 / kapacita.
  2. Projdi reziduální graf do šířky a najdi nejkratší cestu zdroj→spotřebič s volnou kapacitou.
  3. Protlač tok rovný nejmenší reziduální kapacitě podél té cesty.
  4. Aktualizuj rezidua (včetně zpětných hran) a opakuj, dokud cesta zbývá.

Pseudokód

1edmondsKarp(graph, source, sink):   # O(V·E²)2  residual ← capacities; flow ← 03  while a path source→sink exists in the residual (BFS):4    b ← min residual capacity along that path5    for each edge u→v on the path:6      residual[u][v] −= b;  residual[v][u] += b7    flow ← flow + b8  return flow                         # = min cut