Ford-Fulkerson

Gitt et flytnett og et Restnett - Residual Network, returnes den maksimale flyten.

---

Kjøretid: $O(E|f^{\ast }|)$, der $f^{\ast }$ er Maksimal flyt - Maximum flow.

Pseukode til pseudokoden

Virkemåte

Ved første steg har vi ingen flyt ennå, så derfor ser flytnettet og Restnett - Residual Network vårt slik ut: Algoritmen tar grådige valg (Grådige algoritmer), og leter alltid etter en Forøkende sti - Augmenting Path.

Sentral formel er

$$(u,v).f=(u,v).f+c_f(p)$$

Hvor $c_f$ er flaskehalsen i restnettet, altså $c_f(p)=min(\cdot ,\cdot ,\dots )$.

I tilfellet over kommer vi til å omdirigere flyt.