Algoritmo de Flujo Máximo en Redes Dirigidas

Clase 38 de 40 • Curso de Matemáticas Discretas

Clase anteriorSiguiente clase

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:

  1.    Direccionar los flujos e iniciar en ceros.

  2.    Obtener trayectorias buscando el mayor flujo.

  3.    Escoger el menor flujo de la trayectoria, esto es la arista de menor valor dentro de tu camino que seleccionaste.

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

  5.    Buscar nueva trayectoria o camina en aumento y repetir hasta que no existan más.