Algoritmo de Ford-Fulkerson

Algoritmo para calcular el flujo máximo en una red de flujo (equivalentemente; el corte mínimo)

El método Ford-Fulkerson o algoritmo Ford-Fulkerson ( FFA ) es un algoritmo codicioso que calcula el flujo máximo en una red de flujo . A veces se le llama "método" en lugar de "algoritmo", ya que el enfoque para encontrar rutas de aumento en un gráfico residual no está completamente especificado ^[1] o se especifica en varias implementaciones con diferentes tiempos de ejecución. ^[2] Fue publicado en 1956 por LR Ford Jr. y DR Fulkerson . ^[3] El nombre "Ford-Fulkerson" también se utiliza a menudo para el algoritmo de Edmonds-Karp , que es una implementación completamente definida del método Ford-Fulkerson.

La idea detrás del algoritmo es la siguiente: siempre que haya una ruta desde la fuente (nodo inicial) hasta el sumidero (nodo final), con capacidad disponible en todos los bordes de la ruta, enviamos flujo a lo largo de una de las rutas. Luego encontramos otro camino, y así sucesivamente. Un camino con capacidad disponible se llama camino aumentante .

Algoritmo

Sea una gráfica, y para cada arista de u a v , sea la capacidad y sea el flujo. Queremos encontrar el flujo máximo desde la fuente s hasta el sumidero t . Después de cada paso del algoritmo se mantiene lo siguiente: ${\displaystyle G(V,E)}$ ${\displaystyle c(u,v)}$ ${\displaystyle f(u,v)}$

Esto significa que el flujo a través de la red es un flujo legal después de cada ronda del algoritmo. Definimos la red residual como la red con capacidad y sin flujo. Tenga en cuenta que puede suceder que se permita un flujo de v a u en la red residual, aunque no esté permitido en la red original: if y then . ${\displaystyle G_{f}(V,E_{f})}$ ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ ${\displaystyle f(u,v)>0}$ ${\displaystyle c(v,u)=0}$ ${\displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0}$

Algoritmo Ford-Fulkerson

Entradas Dada una red con capacidad de flujo c , un nodo fuente s y un nodo sumidero t ${\displaystyle G=(V,E)}$

Salida Calcular un flujo f de s a t de valor máximo

1. ${\displaystyle f(u,v)\leftarrow 0}$para todos los bordes ${\displaystyle (u,v)}$
2. Si bien hay un camino p de s a t in , tal que para todos los bordes : ${\displaystyle G_{f}}$ ${\displaystyle c_{f}(u,v)>0}$ ${\displaystyle (u,v)\in p}$
   1. Encontrar ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v):(u,v)\in p\}}$
   2. Para cada borde ${\displaystyle (u,v)\in p}$
      1. ${\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)}$( Enviar flujo a lo largo del camino )
      2. ${\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}$( El flujo podría "devolverse" más tarde )

• "←" indica asignación . Por ejemplo, " mayor ← artículo " significa que el valor del mayor cambia al valor del artículo .
• " return " finaliza el algoritmo y genera el siguiente valor.

La ruta en el paso 2 se puede encontrar, por ejemplo, con la búsqueda en amplitud (BFS) o la búsqueda en profundidad en . El primero se conoce como algoritmo de Edmonds-Karp . ${\displaystyle G_{f}(V,E_{f})}$

Cuando no se puedan encontrar más rutas en el paso 2, s no podrá alcanzar t en la red residual. Si S es el conjunto de nodos alcanzables por s en la red residual, entonces la capacidad total en la red original de bordes desde S hasta el resto de V es, por un lado, igual al flujo total que encontramos de s a t , y por otro lado, sirve como límite superior para todos esos flujos. Esto prueba que el flujo que encontramos es máximo. Véase también Teorema de flujo máximo y corte mínimo .

Si el gráfico tiene múltiples fuentes y sumideros, actuamos de la siguiente manera: Supongamos que y . Agregue una nueva fuente con una ventaja desde cada nodo , con capacidad . Y añadir un nuevo fregadero con un borde desde cada nodo hasta , con capacidad . Luego aplique el algoritmo de Ford-Fulkerson. ${\displaystyle G(V,E)}$ ${\displaystyle T=\{t\mid t{\text{ is a sink}}\}}$ ${\displaystyle S=\{s\mid s{\text{ is a source}}\}}$ ${\displaystyle s^{*}}$ ${\displaystyle (s^{*},s)}$ ${\displaystyle s^{*}}$ ${\displaystyle s\in S}$ ${\displaystyle c(s^{*},s)=d_{s}=\sum _{(s,u)\in E}c(s,u)}$ ${\displaystyle t^{*}}$ ${\displaystyle (t,t^{*})}$ ${\displaystyle t\in T}$ ${\displaystyle t^{*}}$ ${\displaystyle c(t,t^{*})=d_{t}=\sum _{(v,t)\in E}c(v,t)}$

Además, si un nodo u tiene restricción de capacidad , reemplazamos este nodo con dos nodos y un borde con capacidad . Luego aplique el algoritmo de Ford-Fulkerson. ${\displaystyle d_{u}}$ ${\displaystyle u_{\mathrm {in} },u_{\mathrm {out} }}$ ${\displaystyle (u_{\mathrm {in} },u_{\mathrm {out} })}$ ${\displaystyle c(u_{\mathrm {in} },u_{\mathrm {out} })=d_{u}}$

Complejidad

Al agregar la ruta de aumento de flujo al flujo ya establecido en el gráfico, se alcanzará el flujo máximo cuando no se puedan encontrar más rutas de aumento de flujo en el gráfico. Sin embargo, no hay certeza de que alguna vez se llegue a esta situación, por lo que lo mejor que se puede garantizar es que la respuesta será correcta si el algoritmo termina. En el caso de que el algoritmo se ejecute indefinidamente, es posible que el flujo ni siquiera converja hacia el flujo máximo. Sin embargo, esta situación sólo ocurre con valores de flujo irracionales. ^[4] Cuando las capacidades son números enteros, el tiempo de ejecución de Ford-Fulkerson está limitado por (ver notación O grande ), donde es el número de aristas en el gráfico y es el flujo máximo en el gráfico. Esto se debe a que cada camino de aumento se puede encontrar en el tiempo y aumenta el flujo en una cantidad entera de al menos , con el límite superior . ${\displaystyle O(Ef)}$ ${\displaystyle E}$ ${\displaystyle f}$ ${\displaystyle O(E)}$ ${\displaystyle 1}$ ${\displaystyle f}$

Una variación del algoritmo Ford-Fulkerson con terminación garantizada y un tiempo de ejecución independiente del valor de flujo máximo es el algoritmo Edmonds-Karp , que se ejecuta en el tiempo. ${\displaystyle O(VE^{2})}$

Ejemplo integral

El siguiente ejemplo muestra los primeros pasos de Ford-Fulkerson en una red de flujo con 4 nodos, fuente y sumidero . Este ejemplo muestra el peor comportamiento del algoritmo. En cada paso, solo se envía un flujo a través de la red. Si en su lugar se utilizara la búsqueda en amplitud, sólo se necesitarían dos pasos. ${\displaystyle A}$ ${\displaystyle D}$ ${\displaystyle 1}$

Observe cómo el flujo "retrocede" desde hacia cuando se encuentra el camino . ${\displaystyle C}$ ${\displaystyle B}$ ${\displaystyle A,C,B,D}$

Ejemplo no terminante

Considere la red de flujo que se muestra a la derecha, con fuente , sumidero , capacidades de los bordes y respectivamente , y la capacidad de todos los demás bordes es un número entero . La constante fue elegida de modo que . Usamos rutas aumentadas de acuerdo con la siguiente tabla, donde y . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{3}}$ ${\displaystyle 1}$ ${\displaystyle r=({\sqrt {5}}-1)/2}$ ${\displaystyle 1}$ ${\displaystyle M\geq 2}$ ${\displaystyle r}$ ${\displaystyle r^{2}=1-r}$ ${\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}$ ${\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\}}$ ${\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\}}$

Tenga en cuenta que después del paso 1 y después del paso 5, las capacidades residuales de los bordes y están en la forma y , respectivamente, para algunos . Esto significa que podemos usar caminos aumentados , e infinitas veces y las capacidades residuales de estos bordes siempre estarán en la misma forma . El flujo total en la red después del paso 5 es . Si continuamos usando caminos aumentantes como se indicó anteriormente, el flujo total converge a . Sin embargo, tenga en cuenta que hay un flujo de valor , al enviar unidades de flujo a lo largo , 1 unidad de flujo a lo largo y unidades de flujo a lo largo . Por lo tanto, el algoritmo nunca termina y el flujo ni siquiera converge al flujo máximo. ^[5] ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{3}}$ ${\displaystyle r^{n}}$ ${\displaystyle r^{n+1}}$ ${\displaystyle 0}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{3}}$ ${\displaystyle 1+2(r^{1}+r^{2})}$ ${\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}$ ${\displaystyle 2M+1}$ ${\displaystyle M}$ ${\displaystyle sv_{1}t}$ ${\displaystyle sv_{2}v_{3}t}$ ${\displaystyle M}$ ${\displaystyle sv_{4}t}$

Backman y Huynh (2018) dan otro ejemplo no terminante basado en el algoritmo euclidiano , donde también muestran que el peor tiempo de ejecución del algoritmo Ford-Fulkerson en una red en números ordinales es . ${\displaystyle G(V,E)}$ ${\displaystyle \omega ^{\Theta (|E|)}}$

Implementación en Python del algoritmo de Edmonds-Karp

importar  colecciones gráfico de clase : """ Esta clase representa un gráfico dirigido usando representación de matriz de adyacencia. """ def  __init__ ( auto ,  gráfico ): ser . gráfico  =  gráfico  # gráfico residual ser . fila  =  len ( gráfico ) def  bfs ( yo ,  s ,  t ,  padre ): """ Devuelve verdadero si hay una ruta desde fuente 's' para hundir 't' en el gráfico residual. También llena parent[] para almacenar la ruta. """ # Marcar todos los vértices como no visitados visitado  =  [ Falso ]  *  yo . fila # Crea una cola para BFS cola  =  colecciones . deque () # Marcar el nodo de origen como visitado y ponerlo en cola cola . agregar ( s ) visitado [ s ]  =  Verdadero # Bucle BFS estándar mientras  cola : u  =  cola . popizquierda () # Obtener todos los vértices adyacentes del vértice u retirado de la cola # Si un adyacente no ha sido visitado, márquelo # visitado y puesto en cola para  ind ,  val  en  enumerar ( self . graph [ u ]): si  ( visitado [ ind ]  ==  False )  y  ( val  >  0 ): cola . añadir ( ind ) visitado [ ind ]  =  Verdadero padre [ ind ]  =  u # Si alcanzamos el sumidero en BFS comenzando desde la fuente, entonces regresamos # verdadero, de lo contrario falso volver  visitado [ t ] # Devuelve el flujo máximo de s a t en el gráfico dado def  edmonds_karp ( auto ,  fuente ,  sumidero ): # Esta matriz se llena con BFS y para almacenar la ruta padre  =  [ -1 ] * yo .​ fila   max_flow  =  0  # No hay flujo inicialmente # Aumentar el flujo mientras haya un camino desde la fuente hasta el sumidero. mientras que  uno mismo . bfs ( fuente ,  receptor ,  padre ): # Encuentre la capacidad residual mínima de los bordes a lo largo del # ruta llena por BFS. O podemos decir encontrar el flujo máximo. # por el camino encontrado. ruta_flujo  =  flotante ( "Inf" ) s  =  fregadero mientras  s  ! =  fuente : path_flow  =  min ( path_flow ,  self . gráfico [ padre [ s ]][ s ]) s  =  padre [ s ] # Agregar flujo de ruta al flujo general flujo_max  +=  flujo_ruta # actualizar capacidades residuales de los bordes y bordes inversos # a lo largo del camino v  =  hundirse mientras  v  ! =  fuente : u  =  padre [ v ] ser . gráfico [ u ][ v ]  -=  flujo_ruta ser . gráfico [ v ][ u ]  +=  flujo_ruta v  =  padre [ v ] devolver  flujo_max

Ver también

• teorema de Berge
• Teorema aproximado de flujo máximo y corte mínimo
• Enrutamiento de restricción de giro
• algoritmo de dinic

Notas

1. Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng (2009). Automatización de diseños electrónicos: síntesis, verificación y prueba . Morgan Kaufman. págs.204. ISBN 978-0080922003.{{cite book}}: CS1 maint: multiple names: authors list (link)
2. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introducción a los algoritmos . Prensa del MIT. págs.714. ISBN 978-0262258104.
3. Ford, LR ; Fulkerson, DR (1956). «Máximo flujo a través de una red» (PDF) . Revista Canadiense de Matemáticas . 8 : 399–404. doi :10.4153/CJM-1956-045-5. S2CID  16109790.
4. "Algoritmo de etiquetado de flujo máximo de Ford-Fulkerson". 1998. CiteSeerX 10.1.1.295.9049 . 
5. Zwick, Uri (21 de agosto de 1995). "Las redes más pequeñas en las que el procedimiento de flujo máximo Ford-Fulkerson puede no terminar". Informática Teórica . 148 (1): 165-170. doi : 10.1016/0304-3975(95)00022-O .

Referencias

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Sección 26.2: El método Ford-Fulkerson". Introducción a los algoritmos (Segunda ed.). MIT Press y McGraw-Hill. págs. 651–664. ISBN 0-262-03293-7.
• George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Capítulo 8: Algoritmos de flujo de red". Algoritmos en pocas palabras . Medios Oreilly . págs. 226–250. ISBN 978-0-596-51624-6.
• Jon Kleinberg ; Eva Tardos (2006). "Capítulo 7: Extensiones al problema del flujo máximo". Diseño de algoritmos . Educación Pearson. págs. 378–384. ISBN 0-321-29535-8.
• Samuel Gutekunst (2019). ENGRI 1101 . Universidad de Cornell.
• Backman, Spencer; Huynh, Tony (2018). "Transfinite Ford-Fulkerson en una red finita". Computabilidad . 7 (4): 341–347. arXiv : 1504.04363 . doi :10.3233/COM-180082. S2CID  15497138.

enlaces externos

• Un tutorial que explica el método Ford-Fulkerson para resolver el problema de flujo máximo
• Otra animación Java
• Aplicación Java Web Start

Medios relacionados con el algoritmo de Ford-Fulkerson en Wikimedia Commons