Algoritmo Ford-Fulkerson: sistemas complejos e inteligencia artificial

Contenido

Algoritmo de Ford-Fulkerson

El algoritmo de Ford-Fulkerson busca un camino creciente en el grafico residual. Satura este camino si existe, de lo contrario devuelve el flujo maximo. Más precisamente, el algoritmo establece un corte mínimo para verificar el criterio de optimalidad. Recuerde que el flujo es menor o igual que el corte.

Para inicializar el algoritmo, es posible atribuir cualquier flujo en el gráfico siguiendo rutas simples (desde la fuente hasta el sumidero). En el siguiente diagrama, hemos tomado la ruta s-2-3-t para la inicialización.

algoritmo de ford-fulkerson flujo máximo problema de flujo máximo gráfico de espacio de corte mínimo flujo creciente

Después de la construcción del gráfico residual, se elige una ruta de sa t si hay una. De lo contrario, tenemos el caudal máximo. En el primer caso, el nuevo flujo se calcula de acuerdo con la ruta creciente elegida en el gráfico de desviación: sumamos el flujo de la ruta creciente al flujo existente si el arco correspondiente en el gráfico original está en la misma dirección que el de la gráfico de desviación, de lo contrario restamos el flujo El algoritmo se detiene cuando ya no hay una ruta creciente.

Es posible formar un corte utilizando el último gráfico de espacios. Aplicamos un camino de s, todos los vértices que se pueden atravesar están en el conjunto S, los demás en el conjunto T. De hecho, los arcos saturados por el flujo cortan el gráfico en dos subconjuntos y forman el valor del corte.

flujo máximo problema de flujo máximo gráfico de desviación de corte mínimo flujo creciente algoritmo ford-fulkerson

Si desea aumentar el flujo cambiando el valor, deberá aumentar el flujo máximo que puede pasar a través de estos arcos.

Algoritmo Ford-Fulkerson paso a paso

El flujo inicial es 0. Aquí el gráfico residual G_F es una copia del gráfico G. Estamos buscando una ruta de sa t, por ejemplo s-2-5-t:

El valor mínimo de la ruta es 8. Agregamos este flujo de 8 a la ruta en el gráfico G.

Como recordatorio, el gráfico residual debe mostrar los arcos inversos (que representan los flujos). El gráfico residual de la nueva iteración es el siguiente:

Aquí elegimos la ruta s-2-3-5-t, con 2 para el flujo de bloqueo. Cuando elegimos un arco inverso (representando así un flujo), el nuevo flujo en el gráfico G se reduce como se muestra en este nuevo gráfico G.