Ford-Fulkersonův algoritmus
Z Wikipedie, otevřené encyklopedie
Ford-Fulkersonův algoritmus (pojmenovaný podle L. R. Forda, Jr. a D. R. Fulkersona) počítá maximální tok v síti. Název Ford-Fulkerson je také často používán pro Edmonds-Karpův algoritmus, který je specializací Ford-Fulkersonova algoritmu.
Myšlenka algoritmu je velmi jednoduchá: Dokud existuje cesta od zdroje (výchozí bod) do spotřebiče (koncový bod), s volnou kapacitou na všech jejích hranách, pošleme tok po jedné z nich. Pak najdeme další takovou cestu, a tak dále. Cesta s volnou kapacitou se nazývá zlepšující cesta.
[editovat] Podívejte se také na
[editovat] Externí odkazy
- Toky v sítích: http://www.cgg.cvut.cz/~zenkar1/36TI/TI36-kap8-A.pdf
- Toky v sítích: http://ksvi.mff.cuni.cz/~dvorak/vyuka/UIN009/Toky.pdf
- Moderní algoritmy pro hledání maximálního toku v síti: http://www.fs.vsb.cz/akce/2001/asr2001/Proceedings/papers/55.pdf

