Dinicův algoritmus
Z Wikipedie, otevřené encyklopedie
Dinicův algoritmus slouží k nalezení maximálního toku v orientovaném grafu.
[editovat] Algoritmus
- vyrobím síť rezerv
- projdu graf z r vlnami a zjistím délku d nejkratší cesty do s
- vyhodím
- hrany ve stejné vrstvě nebo hrany nazpátek (ty nepoužiju - nejkratší cesta jimi jít nemůže)
- a také vrcholy, které tvoří 'slepé uličky' (nevede z nich žádná dopředná hrana)
- a hrany do těchto vrcholů (cyklicky - odstraněním konce slepé uličky, může vzniknout nový konec)
- výsledek kroku 3. nazvu 'čistá síť'
- najdu cestu z r do s délky d
- zjistím minimum m z rezerv na této cestě, zvýším o m tok podél celé cesty, čímž do sítě rezerv přibydou zpětné hrany s rezervou m, a u jedné hrany v cestě zmizí dopředná hrana
- vyčistím síť a pokud zbyde nějaká cesta z r do s délky d, jdu na 5.
- vezmu celou síť a jdu na 2 (nejkratší cesta bude mít délku d+1, ty kratší už v síti rezev nejsou)
- pokud už neexistuje cesta z r do s, skončil jsem (můžu najít i hrany minimálního řezu - jejich počáteční vrcholy jsou konci slepých uliček)
Složitost je O(n2m).