Loading AI tools
De Wikipedia, la enciclopedia libre
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. La idea 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.
Sea un grafo, con vértices, aristas y donde por cada arista , tenemos una capacidad y un flujo . Se busca maximizar el valor del flujo desde una fuente hasta un sumidero .
El método inicia con para toda en . En cada iteración, se incrementa el flujo en mediante el resultado de una búsqueda de un «camino de aumento» en una «red residual» . Aunque cada iteración del método Ford-Fulkerson aumenta el valor del flujo, el flujo por arista de puede aumentar o disminuir. En cada iteración el flujo se aumentara hasta que la red no tenga más caminos de aumento.[1]
El flujo a aumentar se debe considerar legal, para esto debe seguir que.
En una red con fuente s y sumidero t único el valor máximo que puede tomar un flujo variable es igual a la capacidad mínima que puede tomar un corte.
Definimos una red residual como la red donde la capacidad de cada una de las aristas se define como , donde es la capacidad de la arista y el flujo es el flujo de la arista en el camino de aumento seleccionado.
Intuitivamente, dado el grafo y un camino de aumento , la red residual consiste en el grafo que representa el como cambia la capacidad de cada una de las aristas con respecto al flujo del camino de aumento en el grafo .
Un camino de aumento es un camino dirigido de la fuente al sumidero en , donde la capacidad del camino de aumento es el mínimo de las capacidades de sus aristas. Para la elección de un camino de aumento se pueden usar algoritmos ya conocidos, algunos de las más famosos son DFS, BFS, A* o IDA* (Algoritmos de Búsqueda).
Ford-Fulkerson(G,s,t) {
Gf = Crear_grafo_residual(G);
for (cada arista (u,v) de E) {
f[u,v]= 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 arista (u,v) en p) {
f[u,v]= f[u,v] + cf(p);
f[v,u]= f[v,u] - cf(p);
}
Actualizar_grafo_residual(Gf);
}
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.