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 tento kurz
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- 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íť.
