Algoritmo de Ford-Fulkerson

Algoritmo para calcular el caudal máximo en una red

El método Ford–Fulkerson o algoritmo Ford–Fulkerson ( FFA ) es un algoritmo voraz que calcula el flujo máximo en una red de flujo . A veces se lo 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 usa a menudo para el algoritmo 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 exista una ruta desde la fuente (nodo de inicio) hasta el destino (nodo final), con capacidad disponible en todos los bordes de la ruta, enviamos flujo a lo largo de una de las rutas. Luego, encontramos otra ruta, y así sucesivamente. Una ruta con capacidad disponible se denomina ruta de aumento .

Algoritmo

Sea un grafo y, para cada arista de u a v , sea la capacidad y el caudal. Queremos encontrar el caudal 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. Observe que puede suceder que se permita un flujo de v a u en la red residual, aunque no se permita en la red original: si y entonces . ${\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 desde s hasta t de valor máximo

1. ${\displaystyle f(u,v)\leftarrow 0}$Para todos los bordes ${\displaystyle (u,v)}$
2. Mientras exista un camino p desde s hasta t en , tal que para todas las aristas : ${\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)}$( Envía flujo a lo largo de la ruta )
      2. ${\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}$( El flujo podría ser "retornado" más tarde )

• "←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
• " return " finaliza el algoritmo y genera el siguiente valor.

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

Cuando no se pueden encontrar más caminos 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 aristas desde S hasta el resto de V es, por un lado, igual al flujo total que encontramos desde s hasta t y, por otro lado, sirve como límite superior para todos esos flujos. Esto demuestra que el flujo que encontramos es máximo. Véase también Teorema de flujo máximo y corte mínimo .

Si el grafo tiene múltiples fuentes y sumideros, actuamos de la siguiente manera: Supongamos que y . Añadimos una nueva fuente con una arista desde a cada nodo , con capacidad . Y añadimos un nuevo sumidero con una arista desde cada nodo a , con capacidad . A continuación, aplicamos 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 una restricción de capacidad , reemplazamos este nodo con dos nodos , y una arista , con capacidad . Luego aplicamos 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 esta situación se alcance alguna vez, 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 para siempre, el flujo podría ni siquiera converger hacia el flujo máximo. Sin embargo, esta situación solo 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 ruta 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 de Ford-Fulkerson con terminación garantizada y un tiempo de ejecución independiente del valor máximo de flujo es el algoritmo de Edmonds-Karp , que se ejecuta en el tiempo. ${\displaystyle O(VE^{2})}$

Ejemplo de flujo de números enteros

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

Ejemplo sin terminación

Considere la red de flujo que se muestra a la derecha, con fuente , sumidero , capacidades de los bordes , y , y la capacidad de todos los demás bordes algún entero . La constante se eligió de modo que . Usamos caminos de aumento de acuerdo con la siguiente tabla, donde , y . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle e_{1}=1}$ ${\displaystyle e_{2}=r=({\sqrt {5}}-1)/2}$ ${\displaystyle e_{3}=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\}}$

Nótese que después del paso 1 así como 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 de aumento , , y 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 de aumento como se indicó anteriormente, el flujo total converge a . Sin embargo, observe que hay un flujo de valor , al enviar unidades de flujo a lo largo de , 1 unidad de flujo a lo largo de , y unidades de flujo a lo largo de . 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 tiempo de ejecución en el peor caso 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 Edmonds-Karp

importar  coleccionesClase  Gráfica : """ Esta clase representa un gráfico dirigido utilizando representación de la matriz de adyacencia. """ def  __init__ ( self ,  gráfico ): self . graph  =  graph  # gráfico residual self . row  =  len ( gráfico ) def  bfs ( self ,  s ,  t ,  padre ): """ Devuelve verdadero si hay una ruta desde fuente 's' al sumidero 't' en el gráfico residual. También llena parent[] para almacenar la ruta. """ # Marcar todos los vértices como no visitados visitado  =  [ Falso ]  *  self . row # Crear una cola para BFS cola  =  colecciones . deque () # Marcar el nodo de origen como visitado y ponerlo en cola cola .add ( s )​ visitado [ s ]  =  Verdadero # Bucle BFS estándar mientras  cola : u  =  cola . popleft () # Obtener todos los vértices adyacentes del vértice desencolado u # Si no se ha visitado un adyacente, márquelo # lo visitó y lo puso en cola para  ind ,  val  en  enumerate ( self.graph [ u ] ) : si  ( visitó [ ind ]  ==  Falso )  y  ( val  >  0 ): cola .append ( ind )​ visitó [ ind ]  =  Verdadero padre [ ind ]  =  u # Si llegamos al 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 ( self ,  fuente ,  sumidero ): # Esta matriz se llena con BFS y para almacenar la ruta padre  =  [ - 1 ]  *  self . fila max_flow  =  0  # No hay flujo inicialmente # Aumentar el flujo mientras haya una ruta desde la fuente hasta el sumidero mientras  self . bfs ( fuente ,  receptor ,  padre ): # Encuentra la capacidad residual mínima de los bordes a lo largo de la # ruta completada por BFS. O podemos decir que encontramos el caudal máximo # a través de la ruta encontrada. path_flow  =  float ( "Inf" ) s  =  hundirse mientras  s  !=  fuente : path_flow  =  min ( path_flow ,  self . graph [ padre [ s ]][ s ]) s  =  padre [ s ] # Agregar flujo de ruta al flujo general flujo_máximo  +=  flujo_ruta # Actualizar las capacidades residuales de los bordes y bordes inversos. # a lo largo del camino v  =  hundirse mientras  v  !=  fuente : u  =  padre [ v ] auto . grafo [ u ][ v ]  -=  flujo_de_ruta auto . grafo [ v ][ u ]  +=  flujo_de_ruta v  =  padre [ v ] devolver  flujo máximo

Véase también

• Teorema de Berge
• Teorema aproximado de flujo máximo y corte mínimo
• Ruta de restricción de giro
• Algoritmo de Dinic

Notas

1. Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng (2009). Automatización del diseño electrónico: síntesis, verificación y prueba . Morgan Kaufmann. pp. 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). "Flujo máximo 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 de Ford-Fulkerson puede no terminar". Ciencias Informáticas Teóricas . 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 edición). 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 . Oreilly Media . Págs. 226–250. ISBN. 978-0-596-51624-6.
• Jon Kleinberg ; Éva Tardos (2006). "Capítulo 7: Extensiones al problema de flujo máximo". Diseño de algoritmos . Pearson Education. págs. 378–384. ISBN 0-321-29535-8.
• Samuel Gutekunst (2019). ENGRI 1101 . Universidad de Cornell.
• Backman, Spencer; Huynh, Tony (2018). "Ford–Fulkerson transfinito 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 caudal máximo
• Otra animación de Java
• Aplicación Java Web Start

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