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