Si os cuesta entenderlo ayuda imaginarlo como tuberías con distinto caudal. La tubería que va de A a C tiene un caudal de 7, pero como la tubería que va de C a F solo tiene un caudal de 4, la tubería inicial mandará la máxima capacidad (4) y se quedará con la resta (3). La siguiente tubería, como tiene el máximo porque la tubería anterior era mayor, quedará a 0. Y así con todo.
Recursos
Resumen
Habrá ocasiones donde no vamos a querer el coste mínimo, sino buscar el flujo máximo, para esas ocasiones nos servirá este algoritmo. Para este algoritmo usaremos un grafo dirigido empoderado.
Los pasos del algoritmo son los siguientes:
-
Direccionar los flujos e iniciar en ceros. -
Obtener trayectorias buscando el mayor flujo. -
Escoger el menor flujo de la trayectoria, esto es la arista de menor valor dentro de tu camino que seleccionaste. -
Actualizar el gráfico con las capacidades mínimas, ósea, restando el valor de la arista del anterior paso a cada una de las aristas del camino. -
Buscar nueva trayectoria o camina en aumento y repetir hasta que no existan más.