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.

Introducción

Sea G ( V , E ) {\displaystyle G(V,E)} un grafo, con V {\displaystyle V} vértices, E {\displaystyle E} aristas y donde por cada arista ( u , v ) {\displaystyle (u,v)} , tenemos una capacidad c ( u , v ) {\displaystyle c(u,v)} y un flujo f ( u , v ) {\displaystyle f(u,v)} . Se busca maximizar el valor del flujo desde una fuente s {\displaystyle s} hasta un sumidero t {\displaystyle t} .

El método inicia con f ( u , v ) = 0 {\displaystyle f(u,v)=0} para toda ( u , v ) {\displaystyle (u,v)} en V {\displaystyle V} . En cada iteración, se incrementa el flujo en G {\displaystyle G} mediante el resultado de una búsqueda de un «camino de aumento» en una «red residual» G f {\displaystyle G_{f}} . Aunque cada iteración del método Ford-Fulkerson aumenta el valor del flujo, el flujo por arista de G {\displaystyle G} puede aumentar o disminuir. En cada iteración el flujo se aumentara hasta que la red G f {\displaystyle G_{f}} no tenga más caminos de aumento.[1]​

El flujo a aumentar se debe considerar legal, para esto debe seguir que.

  • El flujo de para toda arista ( u , v ) {\displaystyle (u,v)} no debe ser mayor que la capacidad de dicha arista.
  • El flujo que sale de la fuente s {\displaystyle s} debe ser igual al que llega al sumidero t {\displaystyle t} .
Red Residual G f {\displaystyle G_{f}}

Definimos una red residual G f ( V , E ) {\displaystyle G_{f}(V,E)} como la red donde la capacidad de cada una de las aristas se define como c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} , donde c ( u , v ) {\displaystyle c(u,v)} es la capacidad de la arista y el flujo f ( u , v ) {\displaystyle f(u,v)} es el flujo de la arista ( u , v ) {\displaystyle (u,v)} en el camino de aumento seleccionado.

Intuitivamente, dado el grafo G {\displaystyle G} y un camino de aumento c F {\displaystyle c_{F}} , la red residual G f {\displaystyle G_{f}} consiste en el grafo que representa el como cambia la capacidad de cada una de las aristas con respecto al flujo del camino de aumento c F {\displaystyle c_{F}} en el grafo G {\displaystyle G} .

Caminos de Aumento

Un camino de aumento es un camino dirigido de la fuente s {\displaystyle s} al sumidero t {\displaystyle t} en G f {\displaystyle G_{f}} , donde la capacidad del camino de aumento es el mínimo de las capacidades de sus aristas. Para la elección de un camino de aumento se pueden usar algoritmos ya conocidos, algunos de las más famosos son DFS, BFS, A* o IDA* (Algoritmos de Búsqueda).

Pseudocódigo

Referencias

Enlaces externos

  • Animación del algoritmo de Ford-Fulkerson.
  • Wikimedia Commons alberga una categoría multimedia sobre Algoritmo de Ford-Fulkerson.

Algoritmo de FordFulkerson by Rodolfo Lopez Lopez on Prezi

SOLVED Practical No 8 FordFulkerson Algorithm Find the maximum flow

PPT The FordFulkerson Algorithm PowerPoint Presentation, free

Algoritmo de FordFulkerson 02

Solved Perform FordFulkerson algorithm on the following