Algoritmo de Ford-Fulkerson

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 un "algoritmo" ya que el enfoque para encontrar rutas de aumento en un gráfico residual no está completamente especificado o está especificado en varias implementaciones con diferentes tiempos de ejecución. Fue publicado en 1956 por L. R. Ford Jr. y D. R. Fulkerson. El nombre "Ford–Fulkerson" a menudo también se usa 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 haya una ruta desde el origen (nodo inicial) hasta el sumidero (nodo final), con capacidad disponible en todos los bordes de la ruta, enviamos flujo a lo largo de uno de los caminos Luego encontramos otro camino, y así sucesivamente. Una ruta con capacidad disponible se denomina ruta de aumento.

Algoritmo

Vamos G()V,E){displaystyle G(V,E)} ser un gráfico, y para cada borde de u a v, vamos c()u,v){displaystyle c(u,v)} ser la capacidad y f()u,v){displaystyle f(u,v)} sea el flujo. Queremos encontrar el flujo máximo de la fuente s al sumidero t. Después de cada paso en el algoritmo se mantiene lo siguiente:

Limitaciones de la capacidad	О О ()u,v)▪ ▪ E:f()u,v)≤ ≤ c()u,v){displaystyle forall (u,v)in E: f(u,v)leq c(u,v)}	El flujo a lo largo de un borde no puede exceder su capacidad.
Simetría de Skew	О О ()u,v)▪ ▪ E:f()u,v)=− − f()v,u){displaystyle forall (u,v)in E: f(u,v)=-f(v,u)}	El flujo neto de u a v debe ser lo opuesto al flujo neto de v a u (véase el ejemplo).
Conservación del flujo	О О u▪ ▪ V:uل ل syuل ل t⇒ ⇒ .. w▪ ▪ Vf()u,w)=0{displaystyle forall uin V:uneq s{text{ and }uneq tRightarrow sum _{win V}f(u,w)=0}	El flujo neto a un nodo es cero, excepto por la fuente, que "produce" el flujo, y el fregadero, que "consume" el flujo.
Valor f)	.. ()s,u)▪ ▪ Ef()s,u)=.. ()v,t)▪ ▪ Ef()v,t){displaystyle sum _{(s,u)in E}f(s,u)=sum _{(v,t)in E}f(v,t)}	El flujo que sale de s debe ser igual al flujo que llega t.

Esto significa que el flujo a través de la red es un corrientes jurídicas después de cada ronda en el algoritmo. Definimos el Red residual Gf()V,Ef){displaystyle G_{f}(V,E_{f})} ser la red con capacidad cf()u,v)=c()u,v)− − f()u,v){displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} y sin flujo. Observe que puede suceder que un flujo de v a u se permite en el residual red, aunque desacoplada en la red original: si 0}" xmlns="http://www.w3.org/1998/Math/MathML">f()u,v)■0{displaystyle f(u,v)}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dae14fe5525cb06c97321588ea0cc15415f296f1" style="vertical-align: -0.838ex; width:10.84ex; height:2.843ex;"/> y c()v,u)=0{displaystyle c(v,u)=0} entonces 0}" xmlns="http://www.w3.org/1998/Math/MathML">cf()v,u)=c()v,u)− − f()v,u)=f()u,v)■0{displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9f57f50a9829b1ad78a9db1a6e9ec7805233f16c" style="vertical-align: -1.005ex; width:40.208ex; height:3.009ex;"/>.

Algoritm Ford-Fulkerson

El camino en el paso 2 se puede encontrar con, por ejemplo, una búsqueda panorámica (BFS) o una búsqueda de profundidad en Gf()V,Ef){displaystyle G_{f}(V,E_{f})}. Si usas el anterior, el algoritmo se llama Edmonds–Karp.

Cuando no se puedan encontrar más rutas en el paso 2, s no podrá llegar a t en el residual red. Si S es el conjunto de nodos accesibles por s en la red residual, entonces el total capacidad en la red original de bordes desde S hasta el resto de V está 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 prueba que el flujo que encontramos es máximo. Véase también el teorema de Max-flow Min-cut.

Si el gráfico G()V,E){displaystyle G(V,E)} tiene múltiples fuentes y sumideros, actuamos como sigue: Supongamos que T={}t▪ ▪ tes un lavabo}{displaystyle Es un fregadero. y S={}s▪ ▪ ses una fuente}{displaystyle Es una fuente.. Añadir una nueva fuente sAlternativa Alternativa {displaystyle s^{*} con un borde ()sAlternativa Alternativa ,s){displaystyle (s^{*},s)} desde sAlternativa Alternativa {displaystyle s^{*} a todos los nodos s▪ ▪ S{displaystyle sin S}, con capacidad c()sAlternativa Alternativa ,s)=ds=.. ()s,u)▪ ▪ Ec()s,u){displaystyle c(s^{*},s)=d_{s}=sum _{(s,u)in E}c(s,u)}. Y añadir un nuevo fregadero tAlternativa Alternativa {displaystyle t^{*} con un borde ()t,tAlternativa Alternativa ){displaystyle (t,t^{*})} de todos los nodos t▪ ▪ T{displaystyle tin T} a tAlternativa Alternativa {displaystyle t^{*}, con capacidad c()t,tAlternativa Alternativa )=dt=.. ()v,t)▪ ▪ Ec()v,t){displaystyle c(t,t^{*}=d_{t}=sum _{(v,t)in E}c(v,t)}. Luego aplicar el algoritmo Ford-Fulkerson.

También, si un nodo u ha limitado la capacidad du{displaystyle d_{u}, reemplazamos este nodo con dos nodos uin,uout{displaystyle u_{mathrm},u_{mathrm {}, y un borde ()uin,uout){displaystyle (u_{mathrm {in},u_{mathrm {out})}, con capacidad c()uin,uout)=du{displaystyle c(u_{mathrm {in},u_{mathrm {out})=d_{u}. Luego aplicar el algoritmo Ford-Fulkerson.

Complejidad

Añadiendo el camino de aumento del flujo al flujo ya establecido en el gráfico, el flujo máximo se alcanzará cuando ya no se pueden encontrar caminos de aumento del flujo en el gráfico. Sin embargo, no hay certeza de que esta situación se alcance nunca, 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 funcione para siempre, el flujo podría ni siquiera converger hacia el flujo máximo. Sin embargo, esta situación sólo ocurre con valores de flujo irracional. Cuando las capacidades son números enteros, el tiempo de ejecución de Ford-Fulkerson está obligado por O()Ef){displaystyle O(Ef)} (ver gran notación O), donde E{displaystyle E} es el número de bordes en el gráfico y f{displaystyle f} es el flujo máximo en el gráfico. Esto es porque cada camino de aumento se puede encontrar en O()E){displaystyle O(E)} tiempo y aumenta el flujo por una cantidad entero de al menos 1{displaystyle 1}, con el borde superior f{displaystyle f}.

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

Ejemplo integral

El siguiente ejemplo muestra los primeros pasos de Ford-Fulkerson en una red de flujo con 4 nodos, fuente A{displaystyle A} y hundirse D{displaystyle D}. Este ejemplo muestra el peor comportamiento del algoritmo. En cada paso, sólo un flujo de 1{displaystyle 1} es enviado a través de la red. Si se utilizara la primera investigación en su lugar, sólo se necesitarían dos pasos.

Camino	Capacidad	Red de flujo resultante
Red de flujo inicial
A,B,C,D{displaystyle A,B,C,D}	min()cf()A,B),cf()B,C),cf()C,D))=min()c()A,B)− − f()A,B),c()B,C)− − f()B,C),c()C,D)− − f()C,D))=min()1000− − 0,1− − 0,1000− − 0)=1{f}(A,B)-f(A,B),c(B,C),c_{f}(C,D)={}={} {c} {c(A,B)-f(B,C),c(B,C)-f(B,C),c(C,D)-f(C=0}{0}1}
A,C,B,D{displaystyle A,C,B,D}	min()cf()A,C),cf()C,B),cf()B,D))=min()c()A,C)− − f()A,C),c()C,B)− − f()C,B),c()B,D)− − f()B,D))=min()1000− − 0,0− − ()− − 1),1000− − 0)=1{f}(A,C)-f(A,C),c(C,B),c_{f}(B,D)={}={} {f}c(A,C)-f(A,C),c(C,B)-f(C,B),c(B,D)-f(B=0}{0} min}
Después de 1998 más pasos...
Red de flujo final

Observe cómo el flujo es "pushed back" de C{displaystyle C} a B{displaystyle B} cuando encontrar el camino A,C,B,D{displaystyle A,C,B,D}.

Ejemplo de no terminación

Considere la red de flujo mostrada a la derecha, con fuente s{displaystyle s}, lavabo t{displaystyle t}, capacidades de los bordes e1{displaystyle E_{1}, e2{displaystyle E_{2} y e3{displaystyle E_{3} respectivamente 1{displaystyle 1}, r=()5− − 1)/2{displaystyle r=({sqrt {5}-1)/2} y 1{displaystyle 1} y la capacidad de todos los otros bordes algunos enteros M≥ ≥ 2{displaystyle Mgeq 2}. La constante r{displaystyle r} fue elegido así, que r2=1− − r{displaystyle ¿Qué?. Utilizamos caminos de aumento según la tabla siguiente, donde p1={}s,v4,v3,v2,v1,t}{displaystyle ¿Qué?, p2={}s,v2,v3,v4,t}{displaystyle ¿Qué? y p3={}s,v1,v2,v3,t}{displaystyle ¿Qué?.

Paso	Sendero de aumento	Flujo enviado	Capacidades residuales
			e1{displaystyle E_{1}	e2{displaystyle E_{2}	e3{displaystyle E_{3}
0			r0=1{displaystyle - Sí.	r{displaystyle r}	1{displaystyle 1}
1	{}s,v2,v3,t}{displaystyle ¿Qué?	1{displaystyle 1}	r0{displaystyle r^{0}	r1{displaystyle r^{1}	0{displaystyle 0}
2	p1{displaystyle P_{1}	r1{displaystyle r^{1}	r2{displaystyle r^{2}	0{displaystyle 0}	r1{displaystyle r^{1}
3	p2{displaystyle p_{2}	r1{displaystyle r^{1}	r2{displaystyle r^{2}	r1{displaystyle r^{1}	0{displaystyle 0}
4	p1{displaystyle P_{1}	r2{displaystyle r^{2}	0{displaystyle 0}	r3{displaystyle r^{3}	r2{displaystyle r^{2}
5	p3{displaystyle P_{3}	r2{displaystyle r^{2}	r2{displaystyle r^{2}	r3{displaystyle r^{3}	0{displaystyle 0}

Tenga en cuenta que después del paso 1 y después del paso 5, las capacidades residuales de los bordes e1{displaystyle E_{1}, e2{displaystyle E_{2} y e3{displaystyle E_{3} están en la forma rn{displaystyle r^{n}, rn+1{displaystyle r^{n+1} y 0{displaystyle 0}, respectivamente, para algunos n▪ ▪ N{displaystyle nin mathbb {N}. Esto significa que podemos usar caminos de aumento p1{displaystyle P_{1}, p2{displaystyle p_{2}, p1{displaystyle P_{1} y p3{displaystyle P_{3} infinitamente muchas veces y capacidades residuales de estos bordes siempre estarán en la misma forma. Flujo total en la red después del paso 5 es 1+2()r1+r2){displaystyle 1+2(r^{1}+r^{2}}. Si seguimos utilizando caminos de aumento como arriba, el flujo total converge a 1+2.. i=1JUEGO JUEGO ri=3+2r{displaystyle textstyle 1+2sum ¿Qué?. Sin embargo, tenga en cuenta que hay un flujo de valor 2M+1{displaystyle 2M+1}, enviando M{displaystyle M} unidades de flujo sv1t{displaystyle sv_{1}t}, 1 unidad de flujo sv2v3t{displaystyle sv_{2}v_{3}t}, y M{displaystyle M} unidades de flujo sv4t{displaystyle sv_{4}t}. Por lo tanto, el algoritmo nunca termina y el flujo ni siquiera converge al máximo flujo.

Otro ejemplo no-terminante basado en el algoritmo de Euclidean es dado por Backman & Huynh (2018), donde también muestran que el peor caso de tiempo de ejecución del algoritmo de Ford-Fulkerson en una red G()V,E){displaystyle G(V,E)} en números ordinal es ⋅ ⋅ .. ()SilencioESilencio){displaystyle omega ^{Theta (resistentes)}.

Implementación de Python del algoritmo de Edmonds-Karp

importación coleccionesclase Gráfico: ' ' Esta clase representa un gráfico dirigido usando representación de la matriz de adyacencia. ' ' def __init_()auto, Gráfico): auto.Gráfico = Gráfico # gráfico residual auto.fila = Len()Gráfico) def bfs()auto, s, t, padre): ' ' Devoluciones verdaderas si hay un camino desde fuente 's' para hundir 't' en el gráfico residual. También llena a los padres[] para almacenar el camino. ' ' # Marcar todos los vértices como no visitados visitados = [Falso] * auto.fila # Crear una cola para BFS queue = colecciones.deque() # Marque el nodo de la fuente como visitado y enqueue queue.apéndice()s) visitados[s] = Cierto. # Standard BFS loop mientras queue: u = queue.popleft() # Obtener todos los vértices adyacentes del vertex desgarrado u # Si no se ha visitado un adyacente, marquelo # visite y enqueue it para ind, val dentro enumerado()auto.Gráfico[u] si ()visitados[ind] == Falso) y ()val ■ 0): queue.apéndice()ind) visitados[ind] = Cierto. padre[ind] = u # Si alcanzamos el sumidero en BFS a partir de la fuente, entonces regrese # true, else false retorno visitados[t] # Devuelve el flujo máximo de s a t en el gráfico dado def edmonds_karp()auto, fuente, fregadero): # Esta matriz está llenada por BFS y para almacenar la ruta padre = [-1] * auto.fila max_flow = 0 # No hay flujo inicialmente # Aumentar el flujo mientras hay camino de la fuente a la huida mientras auto.bfs()fuente, fregadero, padre): # Encontrar la capacidad residual mínima de los bordes a lo largo de los # Camino lleno por BFS. O podemos decir encontrar el flujo máximo Por el camino encontrado. path_flow = flotador()"Inf") s = fregadero mientras s ! fuente: path_flow = min()path_flow, auto.Gráfico[padre[s]s]) s = padre[s] # Añada el flujo de ruta al flujo general max_flow += path_flow # Actualizar las capacidades residuales de los bordes y los bordes inversos # Por el camino v = fregadero mientras v ! fuente: u = padre[v] auto.Gráfico[u[ ]v] -= path_flow auto.Gráfico[v[ ]u] += path_flow v = padre[v] retorno max_flow