Algoritmo de Ford-Fulkerson



En 1962, L. R. Ford y D. R. Fulkerson desarrollaron una técnica efectiva para resolver problemas de flujo máximo. Es un método genérico para aumentar la capacidad de los flujos incrementalmente a lo largo de los caminos que van del origen al destino, que sirve como la base para un familia de algoritmos. Esta técnica es conocida como el método Ford-Fulkerson en la literatura clásica, aunque también puede encontrarse como el aumenting-path method.



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. y D. R. Fulkerson.

Considérese cualquier camino dirigido del origen al destino en la red de flujos. Sea x la mínima de las capacidades de las aristas no usadas en el camino. Es posible incrementar el flujo de la red al menos en x, incrementando el flujo de las aristas del camino en dicho monto. De esta forma se obtiene el primer intento de flujo en la red. Luego debemos encontrar otro camino, incrementar el flujo en el camino, y continuar hasta que todos los caminos del origen al destino tengan al menos una arista llena (el flujo usa toda la capacidad de la arista).
Las siguientes figuras ilustran el funcionamiento de esta estrategia sobre el grafo de ejemplo. La secuencia de ilustraciones va de izquierda a derecha

FlujoMax1.png
FlujoMax1.png




Aunque esta estrategia calcula el flujo máximo en varios casos, también falla en muchos otros. Para mejorar el algoritmo de tal manera de que siempre encuentre el flujo máximo, se debe considerar una manera más general de incrementar el flujo de origen a destino a través del grafo no dirigido subyacente. Las aristas de cualquier camino del origen al destino avanzan o retroceden.
Las aristas que avanzan van con el flujo y las que retroceden van en sentido contrario al flujo. Ahora bien, para cada camino que no tenga aristas llenas que avancen ni aristas vacías (flujo cero) que retrocedan, podemos incrementar la cantidad de flujo en la red incrementando el flujo en las aristas que avanzan y decrementándo lo en las aristas que retroceden. La cantidad en la que el flujo puede ser incrementado está limitada por la mínima capacidad que no haya sido usada en las aristas que avanzan y los flujos de las aristas que retroceden.
Las siguientes figuras ilustran el funcionamiento de esta última estrategia en un nuevo grafo de ejemplo. La secuencia de ilustraciones va de izquierda a derecha y de arriba hacia abajo.

FlujoMax2.png
FlujoMax2.png




Hasta este punto no se han tomado en cuenta las aristas en retroceso y se tiene un flujo cuyo valor es 6. Ahora tratemos el camino 0 -1-2-3, pero usando la arista 2-1 que va en dirección contraria al flujo.
FlujoMax3.png
FlujoMax3.png




Obsérvese que se le resto valor al flujo que retrocede para agregárselo a los que avanzan. Aquí se obtiene un flujo de 7, que es el flujo máximo de esta red. En este momento ya no hay más caminos que no tengan aristas llenas que avancen o aristas vacías que retrocedan y el algoritmo culmina su ejecución.
Este proceso describe la base para el algoritmo clásico de Ford-Fulkerson (aumenting-path method) para problemas de flujo máximo en redes. En resumen:
Se comienza con flujo nulo en todas partes. Luego se incrementa el flujo a lo largo de cualquier camino de origen a destino que no tenga aristas llenas que avancen o aristas vacías que retrocedan. Se continúa hasta que no haya más caminos como estos en la red.
Este método siempre encuentra el flujo máximo, sin importar como se escojan los caminos.
Cuando las capacidades son valores enteros, el flujo se incrementa en al menos una unidad en cada iteración, así que la terminación es finita. Más aún, para un grafo con V nodos y A aristas con capacidades enteras positivas, el algoritmo ejecuta un máximo de V*A iteraciones para encontrar el flujo máximo. Chvátal describe el caso en el que las capacidades son irracionales.

Método Algoritmo de Ford-Fulkerson


• Este método depende de tres ideas importantes: Camino de aumento y red residual.
• Este método es iterativo. Se comienza con f(u,v) =0 para cada par de nodos.
• En cada iteración se incrementa el valor del flujo buscando un camino de aumento , el cual es un camino desde la fuente al resumidero que puede conducir más flujo.
Ford-Kulkerson_method(G,s,t)
inicializar flujo f a 0;
while (existe un camino de aumento p) do
aumentar el flujo f a lo largo de p;
return f;

• Se repite el proceso previo hasta no encontrar un camino de aumento.
Capacidad residual : es la capacidad adicional de flujo que un arco puede llevar: cf(u,v)= c(u,v)- f(u,v)
• Dado una red de flujo G=(v,E) y un flujo f, la red residual : inducida por f es Gf=(V,Ef), con Ef={(u,v) VxV: Cf(u,v)>0}


Pseudocódigo

Ford-Fulkerson(G,s,t){
for (cada arco (u,v) de E) {
f[u,v]= 0;
f[v,u]= 0;
}
while (exista un camino p desde s at en la red residual Gf) {
cf(p) = min{cf(u,v) : (u,v) está sobre p};
for (cada arco (u,v) en p) {
f[u,v]= f[u,v] + cf(p) ;
f[v,u]= - f[u,v];
}
}
}
Ford-Fulkerson(G,s,t){
for (cada arco (u,v) de E) {
f[u,v]= 0;
f[v,u]= 0;
}
while (exista un camino p desde s at en la red residual Gf)
{
cf(p) = min{cf(u,v) : (u,v) está sobre p};
for (cada arco (u,v) en p) {
f[u,v]= f[u,v] + cf(p) ;
f[v,u]= - f[u,v];
}
}
}