No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Algoritmo de flujo máximo

38/40
Recursos

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.
    

Aportes 36

Preguntas 3

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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.

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

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.

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.

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.

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

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?

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)

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

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

Para los que no entendieron (como yo al principio)
Aquí un video de como resolver el flujo máximo con el Método Ford Fulkerson
https://www.youtube.com/watch?v=AncllC0nGjI
De nada 😉

Para los que no lo entendieron, este vídeo ayuda mucho: https://www.youtube.com/watch?v=BK5OuCEV804&ab_channel=24hVending

Para los que quedaron con dudas como yo, este vídeo les puede servir: https://www.youtube.com/watch?v=FeFXw4IWqSE

Excelente tema y muy bien explicado

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

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

En conclusión, de las 17 unidades que podrían salir de “a”, sólo podemos enviar 13 hasta “g”.

En la segunda pongo los números del color del camino que toma. Espero y se llegue a entender.
En el de abajo a la derecha puse cómo quedarían los flujos que sobrarían y en el último puse los flujos que se utilizaron.

Este curso tiene demasiada información para procesarla.

A LP can Max Z
s.a
Restrictions
Generates a solution

Serviría para medir la capacidad máxima de flujo en vías.

nice

Visitar una vez cada camino, no cada arista

1) Buscar siempre el mayor flujo

Ejercicio demostrativo de Algoritmo de flujo máximo

Genial este algoritmo.

Excelente!

Gracias Profe Sergio

Pregunta… si al definir el camino ACEG con un valor mínimo de 2, el profe restó de A ( 3-2 = 1) ¿por qué al entrar a C no sumó esas 2 a 4 para que a C entraran 6 para que así 4 fueran a F y 2 a E?

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

con lo que me quedo:

  • Se debe enviar lo máximo en cada camino en función de lo que va quedando (hace falta)
  • En el grafo final podemos ver los flujos que llegan a cada vértice
  • Lo que logra enviarse desde el nodo inicial debe se igual a lo que llega en el nodo final

Pensé que este sería el algoritmo más fácil pero me parece complicado 😕

Muy bueno!

Pragmático.