Algoritmo de Flujo Máximo en Redes Dirigidas

Clase 38 de 40 • Curso de Matemáticas Discretas

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.

Antonio Godoy

student•

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.

Martín Valverde

student•

Gracias por el ejemplo, ayuda bastante!

Carlos Eduardo Magallon Zepeda

student•

Ay, ya entendí. ¡Muchas gracias por tomarte el tiempo de explicarlo!

German Tellez Vanegas

student•

Uno de los mejores profesores de platzi, se le da muy bien explicar

Wilson Fernando Antury Torres

student•

Algoritmo de flujo máximo: Encontrar el camino de un punto A a un punto B con la mayor cantidad de flujo.

1: Establecer un grafo dirigido.
2: establecemos todos los vértices en 0
3: establecer caminos desde el punto A hasta el punto B.
4: encontramos la conexión con menor capacidad, pues ésta es quien le dice al camino la capacidad máxima.
5: Hacemos esta iteración hasta que no hayan más caminos.
6: De cada ruta obtenemos un flujo, sumando todos los flujos obtendremos el flujo máximo.

Edwin Nino

student•

Un detalle importante del algoritmo presentado es que al existir flujo sobre una arista se debe generar una arista en dirección opuesta que permita devolver el flujo y enviarlo por otro camino de ser necesario.

Sergio Orduz

teacher•

Gracias por tu aporte edwin.andres has implementado este algoritmo para algún proyecto?

Nicolas Leonardo Anicama Espinoza

student•

Los algoritmos de flujo máximo se aplican a la vida cotidiana para resolver problemas de gestión de recursos, reparto en empresas de logística, control de vuelos con escalas en aerolíneas, gestión de selección de proyectos o para calcular las intensidades máximas en un circuito eléctrico, programación, entre otros.

Ariel Dapia Graziani

student•

El curso es excelente, simple y conciso. Solo tengo una pequeña corrección, no hay que confundir un grafo ponderado con un árbol de expansión. El hecho de que tenga aristas relacionadas a un valor lo convierte en un grafo ponderado. Un árbol de expansión es un grafo con todos los vértices de un grafo no dirigido, sin contener todas las aristas, sino un subconjunto de ellas, manteniendo la conexidad del grafo.

Jhonatan Javier Romero Uriostegui

student•

El camino 1 deberia ser A,C, E, G porque es el que mas flujo tiene.

Josue Noha Valdivia

student•

Algoritmo de flujo máximo Permite hallar el flujo máximo (valor máximo a enviar) entre dos puntos de un grafo dirigido y ponderado, donde cada valor representa el máximo flujo que puede pasar a través de la conexión. Pasos:

Asignar un valor de cero a cada nodo
Elegir un camino por el que se pueda llegar al nodo destino, de preferencia por el que se pueda enviar mayor flujo. Este estará limitado por la arista de menor valor
Actualizar los valores de la arista colocando el flujo que aún pueden recibir y los nodos con el valor de flujo que recibieron.
Iterar con otro camino hasta que ya no existan más caminos posibles (ya no se pude pasar por aristas de valor cero)

Jesús Gabriel Millán Corobo

student•

No entiendo el paso 3 de escoger el menor Flujo, acaso el objetivo no es encontrar el flujo mayor? Porque escogeriamos el menor flujo? En que nos beneficia?

Diego Cesar Lerma Torres

student•

Tenía la misma duda, pero se debe a que el algoritmo toma en cuenta los cuello de botella de enviar más recursos de los que puede soportar el medio por el que se envían.

Entonces en el algoritmo se envía lo máximo, pero lo máximo que pueda soportar el sistema (que se traducirá en que el máximo valor enviado por toda la ruta dependerá de la arista de menor valor, la cual será la que genere el cuello de botella) :D

Miguel Andres Rendon Reyes

student•

El algoritmo de flujo màximo, busca en los grafos dirigidos, encontrar el flujo máximo en estos.

Diego Acero

student•

buenas, Discúlpeme pero este algoritmo no lo entendí nada, solo que del punto A al punto B debe llevar una cantidad max. pero no le entendí nada de como lo llevaba🤔🤔

Emanuel Moreno Manriquez

student•

imagina que tienes un camión de carga de 6 metros de alto y lo debes de llevar por varios puentes, entonces debes planear una ruta donde no pases por ninguna que tenga puentes de menos de 6 metros si no deberás de plantearte usar otro camión u otra ruta pero siempre llevando la mayor cantidad de carga posible. no se vale cambiar de camión a mitad del camino.

César Andrés Romero Alvarado

student•

Hola diogo. estoy ingual de perdido jajajaja

Miguel Andres Rendon Reyes

student•

El grafo tiene que ser dirigido, si no lo es, entonces tienes que dirigir cada conexión.

Usuario anónimo

user•

¿por qué un cuarto camino no pudo ser ACDEG habiendo una disponibilidad de 2?

Jhins Ledys Cárdenas Pardo

student•

Porque la capacidad entre E y G es de 6 y ya reciben esos 6; 2 de C y 4 de D,por lo tanto E no tendría la capacidad de enviarle mas a G.

Sergio Alejandro Martínez

student•

Excelente tema y muy bien explicado

Natalia Caro Barrios

student•

Primero debemos identificar todas las rutas, y después calcular cuál de estas tiene el flujo máximo

Cristian Ignacio Zuñiga Medina

student•

Me queda la duda de que si se pueden repetir los caminos en caso de que admitan mas flujo

Josue Paramaconi Perez Mendoza

student•

No sería mejor en vez de enviar la cantidad menor, enviar el límite que propone la raíz para cada camino? O enviar el máximo que permita una arista en alguna de los camino? Porque no?

Ariel Sharpe

student•

si la raíz tiene capacidad para 7 por ejemplo pero nuestro receptor solo tienen capacidad para 4 perderemos 3 de los 7 datos que mandemos.

Josué David Ortiz Báez

student•

Visitar una vez cada camino, no cada arista

Jhonatan Javier Romero Uriostegui

student•

En el Camino 4 Vertice "E" quedan 2 pero porque se le restan al 4 que ya tenia

Walter Alvarado

student•

nice