Saltar al contenido
Volver a los resultados

Algoritmo de Ford-Fulkerson

Propuesto por
Lester R. Ford and Delbert R. Fulkerson
Año
1956
Tipo
algorithm
Familia
Graph Algorithms

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

El Algoritmo de Ford-Fulkerson, desarrollado por Lester R. Ford y Delbert R. Fulkerson en 1956, es un método fundamental para calcular el flujo máximo en una red de flujo.

Encuentra la cantidad máxima de flujo que puede ser enviada desde una fuente a un sumidero a través de un grafo dirigido con restricciones de capacidad en las aristas.

La intuición detrás del método

El algoritmo funciona encontrando repetidamente caminos aumentantes desde la fuente hasta el sumidero a través de la red residual, donde cada arista tiene capacidad restante. Cada camino contribuye con un flujo adicional igual a su capacidad de cuello de botella (la arista con la menor capacidad restante en el camino). El proceso continúa hasta que no existen más caminos aumentantes, momento en el cual se alcanza el flujo máximo. La idea clave es el teorema de flujo máximo-corte mínimo: el flujo máximo es igual a la capacidad del corte mínimo en la red.

Historia

Ford y Fulkerson introdujeron el problema del flujo máximo y su algoritmo seminal en 1956. El trabajo fue revolucionario, estableciendo tanto un método algorítmico como el célebre teorema de flujo máximo-corte mínimo. Edmonds y Karp (1972) mejoraron la complejidad en el peor de los casos utilizando búsqueda en anchura para la selección de caminos. Avances posteriores de Dinic, Karzanov y otros llevaron a algoritmos aún más rápidos, pero el método de Ford-Fulkerson sigue siendo un algoritmo clásico y pedagógicamente valioso en la informática.

Cuándo usarlo

Aplicar el algoritmo de Ford-Fulkerson para encontrar el flujo máximo en redes de flujo dirigidas o no dirigidas con capacidades enteras positivas. Funciona bien para redes de tamaño pequeño a mediano y proporciona una comprensión intuitiva de los conceptos de flujo en redes. Para redes muy grandes o cuando se requieren flujos integrales, considere Edmonds-Karp (usando BFS) o el algoritmo de Dinic para un mejor rendimiento en el peor de los casos. Úselo cuando la comprensión del comportamiento del algoritmo sea tan importante como la velocidad.

Limitaciones y consideraciones

  • La complejidad temporal depende de los valores de capacidad (no polinomial en general; puede ser exponencial con capacidades irracionales)
  • Puede no converger si las capacidades son irracionales (requiere implementación cuidadosa con aritmética racional)
  • Menos eficiente que algoritmos especializados como Edmonds-Karp o Dinic en redes grandes
  • Sensible al orden de selección de los caminos aumentantes

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Enfoque simple e intuitivo basado en caminos aumentantes
  • Solución óptima garantizada cuando las capacidades son racionales o integrales
  • Eficiente para redes con capacidades enteras pequeñas
  • Forma la base teórica para comprender la dualidad flujo máximo-corte mínimo
  • Funciona con grafos dirigidos y no dirigidos

Aplicaciones

  • Enrutamiento de redes: maximizar el rendimiento de datos desde la fuente hasta el destino en redes de comunicación
  • Redes de transporte: determinar la capacidad máxima de carga entre ciudades considerando restricciones de carreteras y ferrocarriles
  • Emparejamiento bipartito: encontrar emparejamientos máximos en grafos bipartitos construyendo redes de flujo
  • Segmentación de imágenes: usar algoritmos de flujo máximo para particionar imágenes en primer plano y fondo
  • Programación de aerolíneas: optimizar el enrutamiento de aeronaves para maximizar el flujo de pasajeros a través de redes hub-and-spoke
  • Análisis de proteínas: calcular el flujo máximo en redes biológicas para comprender las vías de interacción

Cómo funciona

Cómo funciona

1

Inicializar el grafo residual con capacidades iguales a las capacidades originales de las aristas y flujo cero en todas las aristas.

2

Encontrar un camino aumentante desde la fuente hasta el sumidero en el grafo residual utilizando búsqueda en profundidad o en anchura, calcular la capacidad mínima a lo largo del camino y añadir este flujo a todas las aristas del camino mientras se reducen sus capacidades residuales.

3

Repetir la aumentación hasta que no exista un camino aumentante en el grafo residual; el flujo total acumulado es el flujo máximo.

Errores comunes

  • Elegir caminos aumentantes deficientes que resulten en una convergencia lenta o resultados incorrectos
  • No actualizar correctamente las capacidades residuales o no añadir aristas inversas para deshacer el flujo
  • Usar división entera o aritmética de punto flotante cuando se requiere aritmética exacta para la corrección

Preguntas frecuentes

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

El teorema establece que el flujo máximo desde la fuente hasta el sumidero es igual a la capacidad mínima de cualquier corte que separe la fuente del sumidero. Esto proporciona tanto una visión teórica como un método de verificación para los algoritmos de flujo.

¿Por qué el algoritmo converge a veces lentamente?

Con selecciones de caminos desafortunadas, el algoritmo puede aumentar solo una unidad de flujo por iteración, incluso cuando son posibles aumentos mayores. El uso de búsqueda en anchura (Edmonds-Karp) garantiza una convergencia en tiempo polinomial.

¿Cómo maneja el algoritmo las aristas no dirigidas?

Reemplace cada arista no dirigida con dos aristas dirigidas en direcciones opuestas, ambas con la misma capacidad. El algoritmo luego encuentra el flujo en la red dirigida.

¿Cuál es la diferencia entre el flujo en una arista y la capacidad residual?

El flujo en una arista representa la cantidad de material enviado a lo largo de ella, mientras que la capacidad residual es la capacidad restante disponible. La capacidad residual disminuye a medida que aumenta el flujo, y las aristas inversas rastrean la capacidad de deshacer el flujo.

Métodos relacionados

Fuentes

  1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.

    Abrir referencia DOI
    Copiado.
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

    ISBN: 978-0-262-03384-8
    Copiado.