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 caminos simples (desde la fuente hasta el sumidero). En el siguiente diagrama, tomamos para la inicialización el camino s-2-3-t.

Después de la construcción del gráfico residual, se elige un camino de s a t, si lo hay. De lo contrario tenemos el caudal máximo. En el primer caso, el nuevo caudal se calcula en función de la trayectoria creciente elegida en el gráfico de desviación: el caudal de la trayectoria creciente se suma al caudal existente si el arco correspondiente en el gráfico original tiene la misma dirección que el del gráfico de brecha, de lo contrario se resta el flujo.El algoritmo se detiene cuando ya no hay un camino creciente.

Es posible formar un corte utilizando el último gráfico de desviación. Aplicamos un recorrido desde s, todos los vértices que se pueden recorrer están en el conjunto S, los demás en el conjunto T. En efecto, los arcos saturados por los flujos cortan el gráfico en dos subconjuntos y forman el valor del corte.

Si se desea aumentar el caudal por un cambio de valor, será necesario aumentar el caudal máximo que puede pasar por estos arcos.

El 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.