A Ford-Fulkerson-probléma

Megoldás

Kiválasztunk egy tetszőleges utat a fúrótoronyból az olajfinomítóig. Az úton szereplő legkisebb számot kivonjuk az útban szereplő élekből, és az eredetihez hasonló gráfban (eredetileg itt mindegyik élre -t írunk) ezeket a számokat hozzáadom.

Az algoritmust addig csinálom, ameddig létezik út a fúrótoronyból az olajfinomítóba. A második, általunk létrehozott gráf megadja a feladat megoldását.

A gráfot egy vonallal elvágom. Megnézem, hogy az elvágott vezetékeken keresztül mennyi olaj folyik. Ennél több nem mehet az olajfinomítóba. Ezek közül megkeresem a legkevesebbet. A következő algoritmus erre ad példát.