Lekce 4 - Tok v síti a Dinicův algoritmus na hledání maximálního toku
V minulé lekci, Hledání nejkratší cesty v grafu, jsme hledali nejkratší cestu v orientovaném i neorientovaném grafu pomocí algoritmů Dijkstra a Floyd-Warshall.
Dnes se budeme zabývat toky v síti a hledáním maximálního toku, je tedy dobré znát základní pojmy z teorie grafů, jako např. graf, orientovaný graf, cesta a podobně. Můžete si je osvěžit například v úvodní lekci do teorie grafů.
Motivace
Představme si například vodovodní síť, která je složena z trubek různých velikostí, kte
...konec náhledu článku...
Pokračuj dál
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
Koupit pouze tento kurz
Získej okamžitý přístup ke kurzu bez
časového omezení.
100 Kč
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Přístup k jednotlivým lekcím dle způsobu pořízení.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
Popis článku
Požadovaný článek má následující obsah:
Ukážeme si definice toku v síti, souvisejících pojmů a implementace jednoho z algoritmů na hledání maximálního toku zvaného Dinicův algoritmus.
Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.
