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.
|
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- Animació de l'algorisme de Ford-Fulkerson.