Dinicův algoritmus

Z Wikipedie, otevřené encyklopedie

Dinicův algoritmus slouží k nalezení maximálního toku v orientovaném grafu.

[editovat] Algoritmus

  1. vyrobím síť rezerv
  2. projdu graf z r vlnami a zjistím délku d nejkratší cesty do s
  3. 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)
  4. výsledek kroku 3. nazvu 'čistá síť'
  5. najdu cestu z r do s délky d
  6. 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
  7. vyčistím síť a pokud zbyde nějaká cesta z r do s délky d, jdu na 5.
  8. vezmu celou síť a jdu na 2 (nejkratší cesta bude mít délku d+1, ty kratší už v síti rezev nejsou)
  9. 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).