Důkaz věty „o maximálním toku a minimálním řezu“ je zároveň i návodem jak hledat maximální tok. Začneme s nulovým tokem a postupně budeme hledat vylepšující cesty, podél kterých zvětšíme aktuální tok. Když už nebude existovat vylepšující cesta, tak máme maximální tok. Dostáváme tak Ford-Fulkersonův algoritmus (z roku 1957).

Ford-Fulkerson:
	 $f:=0$
	 while existuje vylepšující cesta $P$ z $s$ do $t$ do
	 	 vylepši tok $f$ podél cesty $P$
	 return $f$

Jak hledat vylepšující cesty si vysvětlíme až v další sekci u Dinicova algoritmu.

Podívejme se, jak je to s konečností Ford-Fulkersonova algoritmu. Pokud má síť celočíselné kapacity, tak v každém kroku stoupne velikost toku alespoň o jedna. Součet všech kapacit, který je horním odhadem na velikost toku, je konečné číslo a proto se algoritmus po konečně mnoha krocích zastaví. Pokud má síť racionální kapacity, tak je můžeme přenásobit nejmenším společným jmenovatelem a tím úlohu převedeme na předchozí případ (průběh algoritmu se tím nezmění). Je zajímavé, že důkaz konečnosti nemůžeme rozšířit na sítě s iracionálními kapacitami. Dokonce existují sítě s iracionálními kapacitami, ve kterých se algoritmus zacyklí (viz třetí z následujících příkladů).

V celočíselné síti zvýšíme tok podél vylepšující cesty vždy o celé číslo. Proto dostáváme následující důsledek.

Důsledek (existence celočíselného toku): V síti s celočíselnými kapacitami hran existuje maximální tok, který je celočíselný.

Příklad: (průběh algoritmu) Najděte maximální tok v síti na následujícím obrázku.

Budeme postupovat podle Ford-Fulkersonova algoritmu. Začneme s nulovým tokem a postupně budeme hledat vylepšující cesty. Průběh algoritmu je naznačen na následujících obrázcích (po řádkách). Každý obrázek zachycuje stav po vylepšení toku podél vyznačené vylepšující cesty.


Po čtvrtém vylepšení už vylepšující cesta neexistuje. Proto je nalezený tok velikosti $5$ maximální. Pokud bychom chtěli najít minimální řez, tak můžeme postupovat podle návodu z důkazu věty o maximálním toku a minimálním řezu. Vylepšující cesta ze zdroje vede jen do vrcholů $\{s, a,c,d,e\}$ a ty také určují minimální řez velikosti $5$.

Příklad (počet iterací závisí na ohodnocení): Doba běhu algoritmu může značně záviset na velikosti kapacit. Podívejme se na následující síť. Pokud budeme střídavě nacházet vylepšující cestu $P_1$ a vylepšující cestu $P_2$, tak budeme muset provést $2N$ vylepšení, než dostaneme maximální tok.


Na příkladu je také vidět, že stačilo vybrat dvě vhodné vylepšující cesty. Jednu vedoucí horem a druhou vedoucí spodem. To nás přivádí k vylepšení, které provedl Edmonds a Karp. Ukázali, že se je výhodné hledat vylepšující cestu s nejmenším počtem hran.

Příklad (zacyklední, Uri Zwick): Pokud jsou kapacity hran reálná čísla, tak se algoritmus může zacyklit. Uvažme síť na následujícím obrázku. Dvě hrany sítě mají kapacitu jedna, šest hran má kapacitu $N$, kde $N$ je dostatečně velké číslo, a jedna hrana má kapacitu $\Phi=(\sqrt{5}-1)/2 \approx 0.618$. Číslo $\Phi$ je zvoleno tak, aby $1-\Phi = \Phi^2$. Přenásobením rovnice členem $\Phi^k$ dostaneme $\Phi^k-\Phi^{k+1} = \Phi^{k+2}$.

V průběhu Ford-Fulkersonova algoritmu budeme na vodorovných hranách sledovat rezervy po směru hrany a zapisovat je zleva doprava do uspořádané trojice. Připomeňme, že rezerva po směru hrany $e$ je $c(e)-f(e)$.

Začneme s nulovým tokem. Vylepšením toku podél cesty $P_1$ dostaneme na vodorovných hranách rezervy $(1, 0, \Phi)$. Dále budeme pracovat jednotlivých iteracích. V každé iteraci postupně provedeme čtyři vylepšení podél cest $P_2$, $P_3$, $P_2$, $P_4$. Předpokládejme, že na začátku iterace jsou rezervy vodorovných hran $(\Phi^{k-1}, 0, \Phi^{k})$. V iteraci postupně zvětšíme tok o $\Phi^k$, $\Phi^k$, $\Phi^{k+1}$ a $\Phi^{k+1}$. Rezervy na vodorovných hranách postupně budou $$ \stackrel{P_2}{\longrightarrow}
(\Phi^{k+1}, \Phi^k, 0) \stackrel{P_3}{\longrightarrow}
(\Phi^{k+1}, 0, \Phi^k) \stackrel{P_2}{\longrightarrow}
(0, \Phi^{k+1}, \Phi^{k+2}) \stackrel{P_4}{\longrightarrow}
(\Phi^{k+1}, 0, \Phi^{k+2})$$ Na konci $n$-té iterace (to je po $4n+1$ vylepšeních) budou rezervy vodorovných hran $\Phi^{2n-2}$, $0$, $\Phi^{2n-1}$. S rostoucím počtem vylepšení konverguje velikost nalezeného toku k hodnotě $$1+2\sum_{i=1}^\infty \Phi^i = \frac{2}{1-\Phi} -1 = 2 + \sqrt{5} \lt 5.$$

Na druhou stranu je zřejmé, že velikost maximálního toku je $2N+1$, kde $N$ je libovolně velké číslo.