Ejemplo Algoritmo para el problema del flujo máximo (IV)

La parte más difícil de este algoritmo, cuando se trabaja con redes muy grandes, es encontrar una trayectoria aumentada. ESta tarea se puede simplificar con un procedimiento sistemático. Se comienza por determinar todos los nodos que se pueden alcanzar desde el origen con un sólo arco con capcidad residual positiva. Después, para caa uno de estos nodos alcanzados, se determinan todos los nuevos nodos (entre los que no han sidos alcanzados) a los que se puede llegar desde este nodo con un solo arco con capacidad residual positiva. Esto se repite con los nuevos nodos conforme se van alcanzando. El resultado será la identificación de un árbol con todos los nodos a los que se puede llegar desde el origen, a lo largo de una trayectoria con capcidad de flujo residual positiva. ESte procedimiento de abanico siempre identificará una trayectoria aumentada, si existe el origen al destino con una capacidad de flujo positivo. En la figura 10.7 se ilustra esto para la red que se obtiene en la iteración 6 del ejemplo anterior.