Calculadora de Flujo Máximo

Pseudocódigo

Todos los algoritmos de flujo máximo de esta familia son el mismo bucle: encuentra un camino del origen al sumidero con capacidad libre, empuja todo lo que permita y repite. Solo se diferencian en cómo eligen ese camino.

FlujoMáximo(grafo, s, t):
    flujo = 0
    construir grafo residual: cap(u,v) directa, 0 inversa

    mientras exista un camino aumentante P de s a t
          en el grafo residual:
        cuello = mínima capacidad residual en P
        para cada arista (u, v) de P:
            residual[u][v] -= cuello
            residual[v][u] += cuello   // arista de deshacer
        flujo += cuello

    devolver flujo

// Ford-Fulkerson: halla P con DFS (cualquier camino)
// Edmonds-Karp:   halla P con BFS (camino más corto)

La arista residual inversa es la parte que parece equivocada y en realidad es esencial. Permite que un camino aumentante posterior cancele flujo empujado antes, y así el algoritmo escapa de una mala elección temprana sin retroceder. Sin esas aristas de deshacer, el bucle voraz se queda atascado en un flujo subóptimo.

Ejemplo resuelto, paso a paso

Ejecuta Edmonds-Karp sobre el ejemplo clásico en el que una primera elección voraz debe deshacerse después.

Grafo de ejemplo: Capacidades dirigidas: S a A (10), S a B (10), A a B (2), A a T (4), B a T (9).

1. Aumento 1. BFS encuentra S a A a T. El cuello de botella es mín(10, 4) = 4. Empuja 4. Flujo total 4. El residual S-A baja a 6 y A-T a 0.
2. Aumento 2. BFS encuentra S a B a T. El cuello de botella es mín(10, 9) = 9. Empuja 9. Flujo total 13. El residual S-B baja a 1 y B-T a 0.
3. Aumento 3. A-T y B-T están saturadas, así que no queda ruta directa. BFS no encuentra ningún camino aumentante: llegar a T exigiría A-T o B-T, y ambas están llenas.
4. Comprobar el corte. ¿Qué aristas están saturadas? A-T con 4 y B-T con 9, capacidad total 13. Quitarlas desconecta T de S, así que es un corte de capacidad 13 y el flujo de 13 lo iguala.
5. Por qué importaría la arista de deshacer. Si el primer camino aumentante hubiera sido S a A a B a T empujando 2, la arista A-B quedaría saturada de una forma que aquí no bloquea nada, pero en grafos donde el camino voraz roba capacidad que un camino posterior necesita, la arista residual inversa B a A permite devolver esas 2 unidades y reencaminarlas. El algoritmo nunca tiene que retroceder de forma explícita.

El flujo máximo es 13, y el corte mínimo es el par de aristas A-T y B-T con capacidad total 13. Que ambos números coincidan no es casualidad: es el teorema de flujo máximo y corte mínimo.

Complejidad y de dónde sale

Tiempo: O(V·E^2) con Edmonds-Karp · Espacio: O(V + E)

Ford-Fulkerson con elección arbitraria de camino corre en O(E por el flujo máximo), porque cada aumento añade al menos una unidad pero la búsqueda del camino cuesta O(E). Eso es pseudopolinómico y realmente malo: con capacidades de mil millones puede requerir mil millones de aumentos, y con capacidades irracionales puede no terminar. Edmonds-Karp lo arregla eligiendo siempre el camino aumentante más corto mediante BFS. La distancia mínima del origen al sumidero nunca decrece, y cada arista puede ser el cuello de botella como mucho V/2 veces, lo que acota los aumentos en O(VE) y el total en O(V por E al cuadrado). Dinic agrupa los aumentos en fases usando un grafo por niveles y lo mejora a O(V al cuadrado por E), u O(E por raíz de V) en grafos de capacidad unitaria.

Cuándo usar Flujo Máximo y cuándo no

La elección depende sobre todo de la magnitud de las capacidades y del tamaño del grafo.

Errores frecuentes

• Omitir las aristas residuales inversas. Sin ellas el algoritmo no puede deshacer un mal aumento anterior y termina en un flujo que solo es maximal, no máximo. Este es el error más común en flujo máximo y produce respuestas plausibles pero demasiado pequeñas.
• Elegir el camino con DFS cuando las capacidades son grandes. Ford-Fulkerson puro con DFS puede necesitar un aumento por unidad de flujo en grafos adversos. El ejemplo clásico, con capacidades de un millón y una arista cuello de botella de uno, requiere un millón de iteraciones. BFS hace que el número no dependa de los valores de capacidad.
• Olvidar que la conservación de flujo excluye origen y sumidero. Todos los demás nodos deben tener flujo entrante igual al saliente. Validar la conservación en el origen o el sumidero fallará siempre y es una fuente habitual de confusión al escribir pruebas.
• Suponer que el flujo máximo es único. El valor del flujo máximo es único; la asignación concreta que lo alcanza normalmente no lo es, ni tampoco el corte mínimo cuando varios tienen la misma capacidad. Las pruebas deben comprobar el valor, no una asignación arista por arista.
• Modelar capacidades de nodo como capacidades de arista. Si un nodo tiene su propio límite de caudal, hay que dividirlo en un nodo de entrada y otro de salida unidos por una arista de esa capacidad. Aplicar el límite a las aristas incidentes plantea un problema distinto e incorrecto.

Preguntas frecuentes

¿Qué es el problema de flujo máximo?

Dado un grafo dirigido donde cada arista tiene una capacidad, más un origen y un sumidero, el flujo máximo pide el mayor caudal al que puede moverse material del origen al sumidero sin superar ninguna capacidad y conservando el flujo en cada nodo intermedio. Modela caudal en tuberías, redes, logística y planificación.

¿Qué es el teorema de flujo máximo y corte mínimo?

El valor del flujo máximo del origen al sumidero siempre iguala la capacidad del corte mínimo que los separa. Intuitivamente, el flujo no puede superar ningún corte porque todo debe cruzarlo, y cuando no queda camino aumentante, los nodos alcanzables en el grafo residual definen un corte cuya capacidad el flujo iguala exactamente.

¿Cuál es la diferencia entre Ford-Fulkerson y Edmonds-Karp?

Son el mismo método de caminos aumentantes con distinta elección de camino. Ford-Fulkerson deja la elección sin especificar, normalmente DFS, lo que hace que el tiempo dependa de los valores de capacidad y pueda ser catastróficamente lento. Edmonds-Karp toma siempre el camino aumentante más corto mediante BFS, lo que acota el trabajo en O(V por E al cuadrado) sean cuales sean las capacidades.

¿Por qué los algoritmos de flujo máximo necesitan aristas residuales?

Porque el algoritmo es voraz y no puede anticiparse. Una arista residual inversa representa la opción de cancelar flujo ya empujado por esa arista, de modo que un camino aumentante posterior puede reencaminar decisiones anteriores. Eso es lo que permite que un bucle que solo avanza alcance un óptimo verdadero sin retroceder.

¿Cuál es la complejidad temporal del flujo máximo?

Edmonds-Karp corre en O(V por E al cuadrado). Dinic lo mejora a O(V al cuadrado por E), y a O(E por la raíz cuadrada de V) en grafos de capacidad unitaria, razón por la que se prefiere para emparejamiento bipartito. Ford-Fulkerson puro es O(E por el valor del flujo máximo), que es pseudopolinómico en lugar de polinómico.