Algoritmo de Ford-Fulkerson

De Wikipedia, la enciclopedia libre

Este artículo o sección sobre informática necesita ser wikificado con un formato adecuado a las convenciones de estilo de Wikipedia. Por favor, edítalo para cumplir con ellas. No elimines este aviso hasta que lo hayas hecho. ¡Colabora wikificando! Copia y pega el siguiente código en la página de discusión del autor: {{subst:Aviso wikificar|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.

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.

[editar] El flujo máximo es la capacidad mínima

[editar] Pseudocódigo del algoritmo

 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]; 
    }  
  } 
 }

Este artículo es un miniesbozo sobre programación en el que falta información esencial. Ampliándolo ayudarás a mejorar Wikipedia. Puedes ayudarte con las wikipedias en otras lenguas.