Ford-Fulkerson obtiene un flujo máximo aumentando repetidamente el flujo a través de caminos de la red residual. Cuando ya no existe un camino desde la fuente hasta el sumidero, el flujo es máximo.
En el tema anterior definimos capacidad, conservación y red residual. Ford-Fulkerson transforma esas ideas en un método general para resolver el problema de flujo máximo.
Se comienza con flujo cero. Mientras la red residual contenga un camino desde la fuente s hasta el sumidero t, se envía por él la mayor cantidad posible.
El flujo cero respeta automáticamente las capacidades y la conservación. Al principio, la capacidad residual hacia adelante coincide con la capacidad original y las aristas inversas tienen capacidad cero.
También es posible comenzar con cualquier flujo factible, aunque la implementación habitual utiliza cero.
Se recorre únicamente la red residual: una arista puede usarse si su capacidad residual es positiva. Una búsqueda en profundidad o en anchura permite encontrar un camino.
Ford-Fulkerson no fija la estrategia de búsqueda. El camino elegido puede cambiar el número de iteraciones, aunque con capacidades enteras el valor final será máximo.
El aumento Δ es la menor capacidad residual de las aristas del camino. Esa arista se saturará después de la actualización.
Enviar una cantidad mayor violaría una capacidad; enviar una menor sería válido, pero desperdiciaría una oportunidad de progreso.
Avanza un camino aumentante por vez. Las aristas verdes forman el camino actual; sus etiquetas muestran flujo/capacidad. La lista lateral muestra la capacidad residual hacia adelante.
Capacidades residuales
Camino aumentante
Acción actual
Al finalizar, las capacidades de entrada al sumidero suman 14 y quedan saturadas. Por ello ningún camino residual puede llegar hasta t.
Si el camino utiliza una arista en su dirección original, se suman Δ unidades a su flujo. Su capacidad residual hacia adelante disminuye en Δ y la inversa aumenta en la misma cantidad.
Si el camino residual recorre v → u para una arista original u → v, se restan Δ unidades del flujo anterior. Esto permite redirigir capacidad hacia una alternativa mejor.
Las aristas inversas son la razón por la que una elección temprana no tiene que ser definitiva.
flujo = 0
mientras exista un camino P desde s hasta t en la red residual:
delta = mínima capacidad residual de P
para cada arista (u, v) de P:
aumentar el flujo si se recorre hacia adelante
disminuir el flujo si se recorre hacia atrás
flujo = flujo + delta
devolver flujofunction buscarCaminoDFS(residual, s, t) {
const padre = Array(residual.length).fill(-1);
const visitado = Array(residual.length).fill(false);
function dfs(u) {
if (u === t) return true;
visitado[u] = true;
for (let v = 0; v < residual.length; v++) {
if (!visitado[v] && residual[u][v] > 0) {
padre[v] = u;
if (dfs(v)) return true;
}
}
return false;
}
return dfs(s) ? padre : null;
}function fordFulkerson(capacidad, s, t) {
const n = capacidad.length;
const residual = capacidad.map(fila => [...fila]);
let flujoMaximo = 0;
let padre;
while ((padre = buscarCaminoDFS(residual, s, t)) !== null) {
let delta = Infinity;
for (let v = t; v !== s; v = padre[v]) {
delta = Math.min(delta, residual[padre[v]][v]);
}
for (let v = t; v !== s; v = padre[v]) {
const u = padre[v];
residual[u][v] -= delta;
residual[v][u] += delta;
}
flujoMaximo += delta;
}
return { flujoMaximo, residual };
}Si se necesita conocer el flujo de cada arista, se conserva una matriz separada o se compara la capacidad original con la residual.
Cuando no existe un camino residual de s a t, tomamos S como los vértices todavía alcanzables desde s y T como el resto. Las aristas originales de S a T están saturadas y las de T a S no transportan flujo neto hacia S.
El valor del flujo coincide entonces con la capacidad del corte (S,T). Por el teorema flujo máximo–corte mínimo, ninguna solución puede ser mejor.
Si todas las capacidades son enteras, cada cuello de botella también lo es y cada iteración aumenta el flujo al menos en una unidad.
Por eso Ford-Fulkerson termina y su complejidad puede expresarse en función del valor máximo |f*|.
Con números irracionales y una elección desafortunada de caminos, el método genérico puede realizar infinitos aumentos y no converger al máximo.
En cálculos con punto flotante también pueden aparecer residuos diminutos por errores numéricos. Conviene utilizar enteros escalados cuando el problema lo permita o establecer una tolerancia.
Edmonds-Karp es una implementación específica de Ford-Fulkerson que siempre busca el camino aumentante con BFS, es decir, con la menor cantidad de aristas.
| Método | Búsqueda | Complejidad |
|---|---|---|
| Ford-Fulkerson con DFS | Cualquier camino | O(E · |f*|) para enteros |
| Edmonds-Karp | BFS | O(VE²) |
Edmonds-Karp ofrece una cota polinómica independiente del valor numérico del flujo máximo.
Una búsqueda DFS cuesta O(E). Con capacidades enteras, hay como máximo |f*| iteraciones si cada una aumenta al menos una unidad.
Esta complejidad es pseudopolinómica: depende del valor de las capacidades, no solo del tamaño de su representación binaria.
Ford-Fulkerson mejora una solución local mediante caminos aumentantes hasta que la red residual proporciona un certificado global de optimalidad. Su idea de avanzar y, cuando sea necesario, deshacer flujo es una de las técnicas más importantes de la teoría de grafos.
En el próximo tema estudiaremos emparejamientos en grafos y veremos cómo una selección de pares compatibles puede expresarse como un problema de flujo.