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.
roční PŘEDPLATNÉ
1 082 Kč
měsíčně, placeno ročně (12 984 Kč)14 000+ lekcí, cvičení a testů
6 000+ ti zůstane napořád
Neomezený přístup ke všem aktuálním
i připravovaným kurzům.
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íš s Provozní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.
