Algoritmo de ford-folkerson

Algoritmo de Ford-Fulkerson
El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. Laidea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, L. R. Ford, Jr. y D. R. Fulkerson.

Algoritmo deFord-Fulkerson
(Nombrado para L. R. Ford, Jr. y D. R. Fulkerson) computa caudal máximo en a red del flujo. Fue publicado en 1956. El nombre “Ford-Fulkerson” a menudo también se utiliza para Algoritmo deEdmonds-Karp, que es una especialización de Ford-Fulkerson.
La idea detrás del algoritmo es muy simple: Mientras haya una trayectoria de la fuente (nodo del comienzo) al fregadero (nodo del final),con capacidad disponible en todos los bordes en la trayectoria, enviamos flujo a lo largo de una de estas trayectorias. Entonces encontramos otra trayectoria, y así sucesivamente. Una trayectoria concapacidad disponible se llama aumentar la trayectoria.

Algoritmo Ford-Fulkerson

Entradas Gráfico con capacidad del flujo, un nodo de la fuente, y un nodo del fregadero

Salida Un flujo de acuál es un máximo
1. para todos los bordes
2. Mientras que hay una trayectoria de a en , tales que para todos los bordes :
1. Hallazgo
2. Para cada borde
1. (Envíeel flujo a lo largo de la trayectoria)
2. (El flujo se pudo “volver” más adelante)

La trayectoria se puede encontrar con por ejemplo a búsqueda breadth-first o a profundidad-primerabúsqueda en Gf(V,Ef). Si usted utiliza el anterior, se llama el algoritmo Edmonds-Karp.

Pseudocódigo

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 a t 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);...