Algoritme de Ford-Fulkerson

L'algoritme de Ford-Fulkerson propon buscar camins en els que es puga aumentar el fluix, fins que s'alcance el fluix màxim. És aplicable als Fluix maximales. L'idea és trobar una ruta de penetració en un fluix positiu net que una els nodos orige i destí. El seu nom ve dau pels seus creadors, L. R. Ford, Jr. i D. R. Fulkerson.

Introducció

Siga $G(V,E)$ un grafo, en $V$ vèrtiços, $E$ arestes i a on per cada aresta $(u,v)$, tenim una capacitat $c(u,v)$ i un fluix $f(u,v)$. Es busca maximizar el valor del fluix des d'una font $s$ fins a un sumidero $t$.

El método inicia en $f(u,v)=0$ per a tota $(u,v)$ en $V$. En cada iteración, s'incrementa el fluix en $G$ per mig del resultat d'una busca d'un «camí d'aument» en una «ret residual» $G_f$. Encara que cada iteración del método Ford-Fulkerson aumenta el valor del fluix, el fluix per aresta de $G$ pot aumentar o disminuir. En cada iteración el fluix s'aumentara fins que la ret $G_f$ no tinga més camins d'aument.

El fluix a aumentar es deu considerar llegal, per a açò deu seguir que.

• El fluix de para tota aresta $(u,v)$ no deu ser major que la capacitat de dita aresta.
• El fluix que ix de la font $s$ deu ser igual al que aplega al sumidero $t$.

En una ret en font s i sumidero t únic el valor màxim que pot prendre un fluix variable és igual a la capacitat mínima que pot prendre un tall.

Teorema

Ret Residual $G_f$

Definim una ret residual $G_f(V,E)$ com la ret a on la capacitat de cada una de les arestes es definix com $c_f(u,v)=c(u,v)-f(u,v)$, a on $c(u,v)$ és la capacitat de l'aresta i el fluix $f(u,v)$ és el fluix de l'aresta $(u,v)$ en el camí d'aument seleccionat.

Intuitivamente, donat el grafo $G$ i un camí d'aument $c_F$, la ret residual $G_f$ consistix en el grafo que representa el com canvia la capacitat de cada una de les arestes sobre el fluix del camí d'aument $c_F$ en el grafo $G$.

Camins d'Aument

Un camí d'aument és un camí dirigit de la font $s$ al sumidero $t$ en $G_f$, a on la capacitat del camí d'aument és el mínim de les capacitats de les seues arestes. Per a l'elecció d'un camí d'aument es poden usar algoritmes ya coneguts, algunes de les més famosos són DFS, BFS, A* o IDA* (Algoritmes de Busca).

Pseudocódigo

 Ford-Fulkerson(G,s,t) { 
    Gf = Crear_grafo_residual(G);
    for (cada aresta (o,v) d'I) { 
        f[o,v]= 0;
    } 
    while (existixca un camí p des de s a t en la ret residual Gf) { 
        cf(p) = min{cf(o,v): (o,v) està sobre p};
        for (cada aresta (o,v) en p) { 
            f[o,v]= f[o,v] + cf(p); 
            f[v,o]= f[v,o] - cf(p); 
        }
        Actualisar_grafo_residual(Gf);
    } 
 }