Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Algoritmo de Ford-Fulkerson

No description
by

Rodolfo Lopez Lopez

on 21 November 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmo de Ford-Fulkerson

1. Definición
El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los vértices origen y destino. Este algoritmo se basa en dos conceptos intuitivos, el de una red residual y el de una trayectoria aumentada. Algunas de sus características son:

• El flujo es siempre positivo y con unidades enteras
• El flujo a través de una arista es menor o igual que la capacidad.
• El flujo que entra en un vértice es igual al que sale de él.

Considérese cualquier camino dirigido del origen al destino en la red de flujos. Sea x la mínima de las capacidades de las aristas no usadas en el camino. Es posible incrementar el flujo de la red al menos en x, incrementando el flujo de las aristas del camino en dicho monto. De esta forma se obtiene el primer intento de flujo en la red. Luego debemos encontrar otro camino, incrementar el flujo en el camino, y continuar hasta que todos los caminos del origen al destino tengan al menos una arista llena (el flujo usa toda la capacidad de la arista). Aunque esta estrategia calcula el flujo máximo en varios casos, también falla en muchos otros.
Para mejorar el algoritmo de tal manera de que siempre encuentre el flujo máximo, se debe considerar una manera más general de incrementar el flujo de origen a destino a través del grafo no dirigido subyacente. Las aristas de cualquier camino del origen al destino avanzan o retroceden. Las aristas que avanzan van con el flujo y las que retroceden van en sentido contrario al flujo. Ahora bien, para cada camino que no tenga aristas llenas que avancen ni aristas vacías (flujo cero) que retrocedan, podemos incrementar la cantidad de flujo en la red incrementando el flujo en las aristas que avanzan y decrementándolo en las aristas que retroceden. La cantidad en la que el flujo puede ser incrementado está limitada por la mínima capacidad que no haya sido usada en las aristas que avanzan y los flujos de las aristas que retroceden.
1.2 Red residual
1.3 Trayectoria aumentada
1.1 Problema que resuelve
Supongamos que se tiene el problema de mandar la mayor cantidad posible de cierto producto desde una ciudad productora “s” a una ciudad demandante “t” pasando posiblemente por otras ciudades de “paso” (ciudades que no son productoras ni demandantes) y que en las rutas a utilizar existe una capacidad máxima de transporte de ese producto.
Algorítmo de Ford-Fulkerson
o Trayectoria de aumento

Por lo tanto, cada trayectoria de aumento proporciona una oportunidad de aumentar más el flujo a través de la red original. El algoritmo de Ford-Fulkerson (trayectoria de aumento) selecciona varias veces una trayectoria de aumento y agrega un flujo igual a su capacidad residual a la trayectoria en la red original. Este proceso continúa hasta que no hay trayectorias de aumento, con lo que el flujo del vértice origen al vértice destino no puede crecer. La clave para asegurar que la solución final es óptima por necesidad es el hecho de que las trayectorias de aumento pueden cancelar flujos asignados con anterioridad en la red original; así, una selección indiscriminada de trayectorias para asignar flujos no puede evitar el uso de una combinación mejor de asignaciones de flujos.
Ejemplo
2. Algoritmo
3. Nomenclaturas
Grafo G al cual sacaremos el flujo máximo mediante el algoritmo de Ford-Fulkerson
4. Ejercicio
1. Se asigna un flujo f de 0 a todas las aristas E.
Flujo máximo = 19
Presentado por:
Ana Karen Martinez Rosales
y
Rodolfo López López
Ford-Fulkerson(G,s,t){
for (cada arco (u,v) de E) {
f[u,v]= 0;
f[v,u]= 0;
}
while (exista un camino p desde s at en la red residual Gf) {
cf(p) = min{cf(u,v) : (u,v) está sobre p};
for (cada arco (u,v) en p) {
f[u,v]= f[u,v] + cf(p) ;
f[v,u]= - f[u,v];
}
}
}


5. Pseudocódigo
Full transcript