# Ford-Fulkerson Algorithm **First known algorithm for solving the [[maximum flow problem]] in [[Flow Network|flow networks]].** > [!Example] Algorithm > $\begin{align} > &\textbf{Algorithm } \text{ Ford-Fulkerson} \\ > \hline > &\textbf{Input: }\text{network $G$ with capacity $c$, source $s$, and sink $t$} \\ > &\textbf{Output: }\text{maximum flow $f$} \\ > \\ > &\text{Let $G_r(V,E_f)$ be the residual network of $G$} \\ > &\text{Assign }f(u,v) = 0 \text{ for all edges } (u,v)\\ > &\textbf{While } \text{there is an augmenting path $p$ from $s$ to $t$ in $G_r$ }\textbf{do}:\\ > &\quad c_f(p)=\min\{c_f(u,v):(u,v)\in p\}\\ > &\quad\text{For each edge $(u,v)\in p$}\\ > &\quad\quad f(u,v)=f(u,v)+c_f(p)\\ > &\quad\quad f(v,u)=f(v,u)-c_f(p)\\ > \\ > &\textbf{return $f$}\\ > \hline > \end{align}$ The *Ford-Fulkerson algorithm* is a [[greedy algorithm]] that involves continually finding [[Flow Network#Augmenting path|augmenting paths]] from the [[Flow Network#Residual network|residual network]] of a flow network and recalculating the flow of the network after augmenting. The maximum flow is attained when there are *no more augmenting paths*. The worst-case [[time complexity]] is $O(E|f|)$ where $E$ is the *number of edges* and $|f|$ is the *maximum flow*, but this only applies on networks with integer capacities. The Ford-Fulkerson algorithm is *incomplete* as it does not specify the method of finding augmented paths and is thus sometimes referred to as the *Ford-Fulkerson method*. The most well-known implementation of the Ford-Fulkerson algorithm is the [[Edmonds-Karp algorithm]]. > [!Example]+ > ![[Ford-FulkersonExample1.svg|450]] > *** > ![[Ford-FulkersonExample2.svg|450]] > *** > ![[Ford-FulkersonExample3.svg|450]] > *** > ![[Ford-FulkersonExample4.svg|450]] > *** > ![[Ford-FulkersonExample5.svg|450]] > *The Ford-Fulkerson algorithm running on a flow network; each iteration is the result of flow augmentation with the augmenting path (red) of the previous flow, updating some of the flow (yellow)* ^324db3