5.3. 5.3. Algoritmus a maximális folyam-minimális vágás feladatpár megoldására

A FORD-FULKERSON tétel bizonyításából, a bizonyítás konstruktív jellege miatt kiolvasható az optimális megoldás megkeresésére szolgáló algoritmust. Ezt az algoritmust a működése miatt növelő út módszernek is nevezhetjük.

  1. A hálózat kiegészítése teljes hálózattá, zérus kapacitású élekkel.

  2. Az induló folyam meghatározása. Amennyiben van induló folyam vagy könnyen találunk ilyet, akkor célszerű abból kiindulni. Legtöbbször azonban az azonosan zérus folyamból indulunk ki, azaz minden élen.

  3. Az induló folyamhoz az éleken az induló szabad kapacitás () meghatározása.

  4. Útkeresés s-ből t-be a telítetlen, azaz éleken (címkézéssel keressük az utat a szabad kapacitású táblázaton, a címkézés során csak a pozitív szabad kapacitásokat kell figyelni).

    Ha nincs út, akkor megállunk, megtaláltuk az optimális megoldáspárt. A minimális vágás a megtalált üres vágás lesz, a maximális folyam pedig a kapacitás és a szabad kapacitás különbsége.

    Ha van út, akkor az (5) ponton folytatjuk az eljárást.

  5. Az út kapacitásának a meghatározása (). Ezt az út mentén a legkisebb szabad kapacitás értéke adja.

  6. Az út kapacitásával az út minden élén növeljük a folyamot. A ferdeszimmetricitás (a visszaáramoltatás biztosítása) miatt a visszút minden élén pedig csökkentjük a folyamot. Gyakorlatban azonban az élekre nem a folyamot, hanem az útkereséshez amúgy is szükséges szabad kapacitást () számítjuk. A szabad kapacitást az út mentén csökkentjük, a visszút mentén pedig növeljük.