El algoritmo de Ford-Fulkerson es un algoritmo genérico para encontrar flujos máximos en una red de transporte. Funciona incrementando gradualmente el flujo a través de la red desde una fuente hasta un sumidero, mientras se buscan "caminos de aumento" en cada paso. El algoritmo termina cuando ya no se pueden encontrar más caminos de aumento, lo que significa que se ha alcanzado el flujo máximo. Este algoritmo es utilizado en problemas de red de transporte, redes de comunicación y otras aplicaciones relacionadas con el flujo de datos.
Este algoritmo nos permite calcular el flujo máximo, tiene como condición trabajar sobre un grafo dirigido.
El grafo mismo me indica dónde empieza y termina, la fuente y el sumidero. La fuente es aquel grafo que solo tiene flechas de salida y el sumidero el que tiene flechas entrantes nada más.
A la hora de trabajar con este algoritmos vamos a armarnos una tabla donde marcamos el flujo real que puede llegar al sumidero.
Cuando hablamos de flujo real nos referimos a que las aristas pueden reducir el peso acumulado, siendo de esta manera el flujo, el último más grande sin pasarse del límite.+
Los números de las aristas nos van a indicar la cantidad de algún elemento que puede conducirse a través de esa arista, supongamos que es agua que fluye a través de caños, entonces si comenzamos por un caño que conduce 16l de agua y luego se encuentra con uno de 9, entonces el flujo se reduce de 16l a 9 litros. Otra cosa que sucede es que se encuentre con espacios más grandes aunque no logre cubrirlos, por ejemplo, si viene en un caño de 7l y se conecta con otro de 14l, los 7l se conducirán normalmente y tendría un espacio libre o sobrante de otros 7l.
Existe otro término que se llama residuo de caudal, este va a ser igual al sobrante de la última arista, supongamos que viene un flujo de 8 y pasa por una última arista de 15, el flujo real es 8 y 7 es el residuo de caudal (15 - 8).