Algoritmo de Ford-Fulkerson
- 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. 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.
Introducción
Sea (V,A,w) con V vértices, A aristas y w peso de las aristas, una red con una única fuente s y un único sumidero t; w(α) es la capacidad de α perteneciente a la arista A. Un flujo f es viable si f(α) <= w(α) para todo α perteneciente a la arista A. Se trata de hallar un flujo viable con el valor máximo posible.
En un 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.
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);
f[v,u]= - f[u,v];
}
}
}
Enlaces externos
Wikimedia foundation.
2010.
Mira otros diccionarios:
Algoritmo de Bellman-Ford — El algoritmo de Bellman Ford (algoritmo de Bell End Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un… … Wikipedia Español
Delbert Ray Fulkerson — Saltar a navegación, búsqueda Delbert Ray Fulkerson Nacimiento 14 de agosto, 1924 Fallecimiento 10 de enero, 1976 Residencia … Wikipedia Español
Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW … Wikipedia Español
Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… … Wikipedia Español
Investigación de operaciones — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar … Wikipedia Español
Vector de distancias — Término usado en redes de comunicaciones para designar un vector que contiene las distancias que un router estima hacia todos los demás routers de la red, de acuerdo con la métrica usada. Los algoritmos de encaminamiento basados en vector de… … Enciclopedia Universal
Red de flujo — Saltar a navegación, búsqueda Entendiendo una red de flujo como un grafo dirigido, donde la fuente es quien produce o inicia el traspaso de algún material o producto por los arcos, estos últimos, vistos como caminos o conductos y tomando en… … Wikipedia Español
Wikimedia Commons alberga contenido multimedia sobre Algoritmo de Ford-Fulkerson. Commons
