Análisis de Ford-Fulkerson

  • Si el camino de aumento es elegido usando breadth-first search (o búsqueda por niveles o amplitud), el algoritmo corre en tiempo polinomial.
  • En este caso el método de Ford-Fulkerson es conocido como algoritmo de Edmonds-Karp.
  • El algoritmo tiene un costo inicial O(E)
  • El cuerpo del loop toma un tiempo O(E) dado que en el ciclo for se procesa cada arco del camino de aumento.
  • Luego se puede demostrar que el número de aumentos de flujo está acotado por O(VE).
  • Esta cota es obtenida considerando que al aumentar el flujo al menos un arco del camino de aumento desaparece (el que tenía capacidad residual mínima. La Eliminación de arcos hace aumentar la distancia desde el nodo de partida. El mismo Arco podría reaparecer posteriormente, pero con distancia aun mayor de la fuente.
  • Así el número de veces que un arco pude aparecer está acotado por el número de nodos -2 (distancia máxima posible). Como hay E arcos, el número total de caminos de aumentos es O(VE).
  • Así el costo del algoritmo es O(VE2)
  • Hay otros algoritmos que obtienen O(V2E) y otro O(V3).