Algoritmo de Ford-
Fulkerson
¿Què es?
El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el
flujo, hasta que se alcance el flujo máximo. La idea es encontrar una ruta de penetración
con un flujo positivo neto que una los vértices origen y destino. Este algoritmo se basa en
dos conceptos intuitivos, el de una red residual y el de una trayectoria aumentada. Algunas
de sus características son:
● El flujo es siempre positivo y con unidades enteras
● El flujo a través de una arista es menor o igual que la capacidad.
● El flujo que entra en un vértice es igual al que sale de él.
Cualidades
Algunas de sus características son:
● El flujo es siempre positivo y con unidades enteras
● El flujo a través de una arista es menor o igual que la capacidad.
● El flujo que entra en un vértice es igual al que sale de él.
Antecedentes
Antes de entender el algoritmo de Ford-Fulkerson, es importante comprender los
conceptos básicos de redes y flujos. Una red consiste en un conjunto de nodos conectados
por arcos. Un flujo es una asignación de cantidades a los arcos de la red, sujeto a
restricciones. El objetivo es encontrar el flujo máximo que se puede enviar desde un nodo
fuente a un nodo sumidero.
En otras palabras…
El algoritmo de Ford-Fulkerson es una técnica utilizada para maximizar el flujo en redes.
Se basa en el concepto de cortes mínimos y utiliza caminos aumentantes para encontrar la
solución óptima. Este algoritmo es ampliamente utilizado en:
❏ Redes de comunicaciones de todo tipo (terrestres, aéreas, telefónicas, etc.).
❏ Distribución de bienes (eléctricas, de aguas, de gas, etc.).
❏ Organización y gestión (servicios, sanidad, seguridad, etc.).
Comprendamos un poco más
Dado un grafo dirigido con pesos,G=(V,A,W),que representa las capacidades
máximas de los canales, un nodo de inicio S y otro de fin T
en V, se trata de encontrar la cantidad máxima de flujo que puede circular desde S
hasta T.
Las aristas representan canales por los que puede circular cierta cosa: transmisión
de datos, redes de corriente eléctrica, líneas de oleoductos, agua, automóviles,etc.
Los pesos de las aristas representan la capacidad máxima de un canal: velocidad
de una conexión,
cantidad máxima de tráfico, voltaje de una línea eléctrica, volumen máximo de
agua, etc.
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). 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 decrementando 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.
Pasos
Inicialización:
● Inicializa el flujo en todos los arcos a cero.
● Define un nodo fuente (source) y un nodo sumidero (sink) en la red.
Encuentra un Camino Aumentante:
● Utiliza un algoritmo de búsqueda (por ejemplo, BFS o DFS) para encontrar un camino desde la fuente hasta
el sumidero en la red residual.
● El camino debe incluir arcos que tengan capacidad residual positiva (capacidad actual - flujo actual > 0).
Calcula el Valor del Flujo del Camino Aumentante:
● Encuentra la capacidad residual mínima en el camino aumentante. Esto se llama "capacidad residual".
● Actualiza el flujo en todos los arcos del camino aumentante sumando la capacidad residual al flujo actual en
esos arcos y restando la misma cantidad de capacidad residual de los arcos inversos en la red residual.
Actualiza la Red Residual:
● Ajusta la red residual disminuyendo la capacidad de los arcos utilizados en el camino aumentante en la
cantidad de capacidad residual y aumentando la capacidad de los arcos inversos en la misma cantidad.
Repite los Pasos 2 a 4:
● Continúa buscando caminos aumentantes y repitiendo los pasos 2 a 4 hasta que no sea posible
encontrar más caminos aumentantes en la red residual.
Resultado:
● Cuando no se pueden encontrar más caminos aumentantes en la red residual, el algoritmo termina. El
flujo máximo se calcula sumando todos los flujos en los arcos que salen de la fuente.
