Algoritmo de Ford-Fulkerson

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 29 de abril de 2022; las comprobaciones requieren 3 ediciones .

El algoritmo de Ford-Fulkerson resuelve el problema de encontrar el flujo máximo en una red de transporte .

La idea del algoritmo es la siguiente. El valor de flujo se establece inicialmente en 0: para todos . Luego, la cantidad de flujo se incrementa iterativamente buscando una ruta de aumento (una ruta desde la fuente hasta el sumidero a lo largo de la cual se puede enviar más flujo). El proceso se repite hasta que se puede encontrar una ruta de aumento. $f(u,v)=0$ $tu,v\en V$ $s$ $t$

Algoritmo

Descripción informal

Restablecemos todas las transmisiones. La red residual coincide inicialmente con la red original.
En la red residual, encontramos cualquier camino desde la fuente hasta el sumidero. Si no existe tal camino, nos detenemos.
Dejamos por el camino encontrado (se llama camino creciente o cadena creciente ) el máximo caudal posible:
1. En el camino encontrado en la red residual, estamos buscando un borde con la capacidad mínima . $c_{\min}$
2. Para cada arista en el camino encontrado, aumentamos el flujo en , y en la dirección opuesta, lo disminuimos en . $c_{\min}$ $c_{\min}$
3. Modificamos la red residual. Para todas las aristas del camino encontrado, así como para las aristas opuestas (antiparalelas) a ellas, calculamos la nueva capacidad. Si se vuelve distinto de cero, agregamos un borde a la red residual, y si se vuelve cero, lo borramos.
Volvemos al paso 2.

Es importante que el algoritmo no especifique exactamente qué camino estamos buscando en el paso 2 ni cómo lo hacemos. Por esta razón, se garantiza que el algoritmo convergerá solo para anchos de banda enteros, pero incluso para ellos, para anchos de banda grandes, puede ejecutarse durante mucho tiempo. Si las capacidades son reales, el algoritmo puede ejecutarse indefinidamente sin converger a la solución óptima (ver ejemplo a continuación ).

Si no buscas ningún camino, sino el más corto, obtienes el algoritmo de Edmonds-Karp o el algoritmo de Dinits . Estos algoritmos convergen para cualquier peso real en el tiempo y respectivamente. $O(|V||E|^{2})$ $O(|V|^{2}|E|)$

Descripción formal

Dado un gráfico con capacidad y flujo para aristas de a . Es necesario encontrar el caudal máximo desde la fuente hasta el sumidero . En cada paso del algoritmo, se aplican las mismas condiciones que para todos los flujos: $G(V,E)$ $c(u,v)$ $f(u,v)=0$ ${\ estilo de visualización u}$ ${\ estilo de visualización v}$ $s$ $t$

$\ 0\leqslant f(u,v)\leqslant c(u,v)$ . El flujo de a no excede el rendimiento. $tu$ $v$
$\f(u,v)=-f(v,u)$ .
$\ \sum _{v}f(u,v)=0\Longleftrightarrow f_{{in}}(u)=f_{{out}}(u)$ para todos los nodos excepto y . El flujo no cambia a medida que pasa por el nodo. $tu$ $s$ $t$

La red residual es una red con ancho de banda y sin flujo. $G_{f}(V,E_{f})$ $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$

Entrada Gráfico con ancho de banda , fuente y sumidero Salida Caudal máximo de a $GRAMO$ $C$ $s$ $t$
$F$ $s$ $t$

${\ estilo de visualización f (u, v): = 0}$ para todos los bordes $(u,v)$
Siempre que haya una ruta de a a tal que para todos los bordes : $pags$ $s$ $t$ $G_f$ ${\ estilo de visualización c_ {f} (u, v)> 0}$ $(u,v)\en p$
1. Encontrar ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\en p\))$
2. Para cada borde $(u,v)\en p$
  1. ${\ estilo de visualización f (u, v): = f (u, v) + c_ {f} (p)}$
  2. $f(v,u):=f(v,u)-c_{f}(p)$
  3. $c_{f}(u,v)=c(u,v)-f(u,v)$
  4. ${\ Displaystyle c_ {f} (v, u) = f (u, v)}$

La ruta se puede encontrar, por ejemplo, mediante la búsqueda en anchura ( algoritmo de Edmonds-Karp ) o la búsqueda en profundidad en . $G_{f}(V,E_{f})$

Dificultad

En cada paso, el algoritmo agrega un flujo de ruta de aumento al flujo existente. Si las capacidades de todos los bordes son números enteros, es fácil demostrar por inducción que los flujos a través de todos los bordes siempre serán números enteros. Por lo tanto, en cada paso, el algoritmo aumenta el flujo en al menos uno, por lo que convergerá en la mayoría de los pasos, donde f es el flujo máximo en el gráfico. Es posible completar cada paso en el tiempo , donde está el número de aristas en el gráfico, entonces el tiempo total de ejecución del algoritmo es limitado . ${\ estilo de visualización O (| f |)}$ ${\ estilo de visualización O (| E |)}$ ${\ estilo de visualización | E |}$ $O(|E|\max |f|)$

Si la capacidad de al menos uno de los bordes es un número irracional, entonces el algoritmo puede ejecutarse indefinidamente, sin converger necesariamente a la solución correcta. A continuación se proporciona un ejemplo.

Un ejemplo de un algoritmo no convergente

Considere la red que se muestra a la derecha, con fuente , sumidero , capacidades de borde y la capacidad de todos los demás bordes igual a un número entero . La constante se elige de modo que . Usamos los caminos del gráfico residual dado en la tabla, y , y . $s$ $t$ ${\ estilo de visualización e_ {1} = 1}$ $e_{2}=r=({\sqrt {5}}-1)/2$ ${\ estilo de visualización e_ {3} = 1}$ $M\geq 2$ $r$ $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\))$

Paso	camino encontrado	Hilo añadido	Capacidades residuales
Paso	camino encontrado	Hilo añadido	$e_{1}$	$e_{2}$	$e_{3}$
0			$r^{0}=1$	$r$	$una$
una	$\{s,v_{2},v_{3},t\}$	$una$	$r^{0}$	$r^{1}$	${\ estilo de visualización 0}$
2	$p_{1}$	$r^{1}$	$r^{2}$	${\ estilo de visualización 0}$	$r^{1}$
3	$p_{2}$	$r^{1}$	$r^{2}$	$r^{1}$	${\ estilo de visualización 0}$
cuatro	$p_{1}$	$r^{2}$	${\ estilo de visualización 0}$	$r^{3}$	$r^{2}$
5	$p_{3}$	$r^{2}$	$r^{2}$	$r^{3}$	${\ estilo de visualización 0}$

Tenga en cuenta que después del paso 1, así como después del paso 5, las capacidades residuales de los bordes , y tienen la forma , y , respectivamente, para algunos naturales . Esto significa que podemos usar rutas de aumento , , e infinitas veces, y la capacidad residual de estos bordes siempre será de la misma forma. El flujo total después del paso 5 es . En un tiempo infinito, el flujo total convergerá a , mientras que el flujo máximo es . Por lo tanto, el algoritmo no solo se ejecuta indefinidamente, sino que ni siquiera converge a la solución óptima. [una] $e_{1}$ $e_{2}$ $e_{3}$ $r^{n}$ $r^{{n+1}}$ ${\ estilo de visualización 0}$ $norte$ $p_{1}$ $p_{2}$ $p_{1}$ $p_{3}$ $1+2(r^{1}+r^{2})$ $\textstyle 1+2\sum_{{i=1}}^{\infty}r^{i}=3+2r$ $2M+1$

Ejemplo

El siguiente ejemplo muestra los primeros pasos del algoritmo Ford-Fulkerson en una red de transporte con cuatro nodos, fuente A y sumidero D. Este ejemplo muestra el peor de los casos. Cuando se usa la búsqueda primero en amplitud, el algoritmo solo necesita 2 pasos.

Sendero	Banda ancha	Resultado
	Red de transporte inicial
$A B C D$	$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(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$
$A,C,B,D$	$\min(c_{f}(A,C),c_{f}(C,B),c_{f}(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$
	Después de 1998 pasos...
	Red de destino

Véase también

Teorema de Ford-Fulkerson

Enlaces

Un ejemplo de resolución de un problema en YouTube
Visualizador de algoritmos
Implementación de la búsqueda del caudal máximo por el método Ford-Fulkerson en Java
Wikimedia Commons tiene medios relacionados con el algoritmo Ford-Fulkerson

Literatura

Thomas H. Kormen et al Algoritmos: construcción y análisis = INTRODUCCIÓN A LOS ALGORITMOS. - 2ª ed. - M. : "Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .

Notas

↑ Zwick, Uri. Las redes más pequeñas en las que el procedimiento de flujo máximo de Ford-Fulkerson puede fallar al terminar // Ciencias de la Computación Teórica : diario. - 1995. - 21 de agosto ( vol. 148 , n. 1 ). - pág. 165-170 . - doi : 10.1016/0304-3975(95)00022-O .