Es una trayectoria dirigida del nodo fuente al nodo destino en la red residual, tal que todos los arcos en esta trayectoria tienen capacidad residual estrictamente positiva. El mínimo de estas capacidades residuales se llama capacidad residual de la trayectoria aumentada porque representa la cantidad de flujo que es factible aumentar en toda la trayectoria. Por lo tanto, cada trayectoria aumentada proporciona una oportunidad de aumentar más el flujo a través de la red original.
El algoritmo de la trayectoria aumentada selecciona repetidas veces algunas trayectoria aumentada y agrega un flujo igual a su capacidad residual en la red original. Este proceso continúa hasta que ya no hay trayectorias aumentadas, con lo que el flujo del nodo fuente al nodo destino no se puede aumentar. La clave para asegurar que la solución final es necesariamente óptima es el hecho de que las trayectorias aumentadas pueden cancelar flujos asignados con anterioridad en la red original; así, una selección indiscriminada de trayectorias para asignar flujos no puede evitar el uso de una combinación mejor de asignaciones de flujos.
Para resumir, cada iteración del algoritmo consiste en los tres pasos siguientes.
No hay comentarios.:
Publicar un comentario