El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo.
Es aplicable a los Flujos maximales.
La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino.
Su nombre viene dado por sus creadores, L. R. Ford, Jr.
Se busca maximizar el valor del flujo desde una fuente
En cada iteración, se incrementa el flujo en
Aunque cada iteración del método Ford-Fulkerson aumenta el valor del flujo, el flujo por arista de
puede aumentar o disminuir.
En cada iteración el flujo se aumentara hasta que la red
no tenga más caminos de aumento.
[1] El flujo a aumentar se debe considerar legal, para esto debe seguir que.
Definimos una red residual
es la capacidad de la arista y el flujo
es el flujo de la arista
en el camino de aumento seleccionado.
Intuitivamente, dado el grafo
y un camino de aumento
consiste en el grafo que representa el como cambia la capacidad de cada una de las aristas con respecto al flujo del camino de aumento
Un camino de aumento es un camino dirigido de la fuente
Para la elección de un camino de aumento se pueden usar algoritmos ya conocidos, algunos de las más famosos son DFS, BFS, A* o IDA* (Algoritmos de Búsqueda).