Minimální řez a maximální tok

Pokračování přednášky TIN060 Algoritmy a datové struktury I
tomas877

Minimální řez a maximální tok

Příspěvek od tomas877 »

Dobrý den,
mám takový problém se kterým si nevím rady, chci naimplementovat hledání maximálního toku pomocí Goldbergova algoritmu v tom problém nemám, ale dále chci s využitím toho že znám maximální tok najít minimální řez. To je pro mě ten problém. Nevíte někdo jak na to?
předem děkuji za všechny odpovědi
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Minimální řez a maximální tok

Příspěvek od Osiris »

tomas877 píše:Dobrý den,
mám takový problém se kterým si nevím rady, chci naimplementovat hledání maximálního toku pomocí Goldbergova algoritmu v tom problém nemám, ale dále chci s využitím toho že znám maximální tok najít minimální řez. To je pro mě ten problém. Nevíte někdo jak na to?
předem děkuji za všechny odpovědi
Proveď jednu "iteraci" FF algoritmu a snadno to zjistíš (hledej nenasycené cesty ze zdroje).
Osiris
tomas877

Re: Minimální řez a maximální tok

Příspěvek od tomas877 »

2Osiris: Díky moc už mi to docvaklo, ani nevim jak jsem mohl bejt tak blbej a nevsimnout si toho:). Fakt díky;)
tomas877

Re: Minimální řez a maximální tok

Příspěvek od tomas877 »

ahoj, já mám ještě takovej malej dotaz, jak se u Goldbergova algoritmu řeší orientované smyčky a druhá věc kam vrátit přebytek, když už ho není kam přeposlat.
díky moc
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“