Algorisme de Ford-Fulkerson

L'algorisme de Ford-Fulkerson és un algorisme que calcula el flux màxim en una xarxa de flux. L'algorisme proposa buscar camins en els quals es pugui augmentar el flux, fins que s'aconsegueixi el flux màxim. La idea és trobar una ruta de penetració amb un flux positiu net que uneixi els nodes origen i destinació. El seu nom ve donat pels seus creadors, L. R. Ford, Jr. i D. R. Fulkerson.

Introducció

Sigui (V,A,w) amb V vèrtexs, A arestes i w el pes de les arestes, una xarxa amb una única font (source) s i un únic embornal (sink) t; w(α) és la capacitat de α pertanyent a l'aresta A. Un flux f és viable si f(α) <= w(α) para tot α pertanyent a l'aresta A. Es tracta de trobar un flux viable amb el valor màxim possible.

En una xarxa amb font s i embornal t únic, el valor màxim que pot prendre un flux variable és igual a la capacitat mínima que pot prendre un tall.

Pseudocodi 

 Ford-Fulkerson(G,s,t)
 { 
 for (cada arc (u,v) de E) 
 { 
 f[u,v]= 0; 
 f[v,u]= 0; 
 } 
 while (existeixi un camí p des de s a t a la xarxa residual Gf) 
 { 
 cf(p) = min{cf(u,v): (u,v) és sobre p};
 for (cada arc (u,v) en p) 
 { 
 f[u,v]= f[u,v] + cf(p); 
 f[v,u]= - f[u,v]; 
 } 
 } 
 }

Enllaços externs

  • Animació de l'algorisme de Ford-Fulkerson.