Algoritmo de Edmonds-Karp

En ciencias de la computación y teoría de grafos, el Algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular el flujo maximal en una red de flujo(i.e. computer network) con complejidad O(V E²). Es asintóticamente más lento que el algoritmo de Push-relabel, que tiene complejidad O(V³), pero es habitualmente más rápido en la práctica para grafos ralos. El algoritmo fue publicado por primera vez por un científico soviético, Yefim (Chaim) Dinic, en 1970,^[1]​ e independientemente por Jack Edmonds y Richard Karp en 1972.^[2]​ El Algoritmo de Dinic incluye técnicas adicionales para reducir la complejidad a O(V²E).

El algoritmo es idéntico al algoritmo de Ford-Fulkerson, excepto porque el orden para ir buscando los caminos aumentantes está definido. El camino encontrado debe ser el camino más corto que tiene capacidad disponible. Esto se puede encontrar mediante una búsqueda en anchura, ya que dejamos que los bordes tengan unidad de longitud. La complejidad O(V E²)^[3]​ se fundamenta mostrando que cada camino aumentante puede ser encontrado con O(E), cada vez que al menos uno de los lados E se satura, la distancia desde el lado saturado hasta el origen a través del camino aumentante deberá ser más largo que la última vez que este estuvo saturado, y ese largo es a lo sumo V. Otra propiedad de este algoritmo es que el largo del camino aumentante más corto se incrementa monotonamente. Hay una prueba accesible en:.^[4]​

Dado un grafo dirigido (network) de 7 nodos, origen A, hundimiento G, y las capacidades que se muestran debajo:

En los pares ${displaystyle f/c}$ escritos en los lados , ${displaystyle f}$ es el flujo actual, y ${displaystyle c}$ es la capacidad. La capacidad de la resta entre ${displaystyle u}$ y ${displaystyle v}$ es ${displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$, la capacidad total, menos el flujo que esta en uso. Si el flujo desde ${displaystyle u}$ a ${displaystyle v}$ es negativo, esto contribuye a la capacidad del residuo.

${displaystyle min(3-0,2-0,1-0)=}$
${displaystyle min(3,2,1)=1}$

${displaystyle min(3-1,6-0,9-0)=}$
${displaystyle min(2,6,9)=2}$

${displaystyle min(3-0,4-0,1-0,6-2,9-2)=}$
${displaystyle min(3,4,1,4,7)=1}$

${displaystyle min(3-1,4-1,2-0,0--1,6-3,9-3)=}$
${displaystyle min(2,3,2,1,3,6)=1}$

Notar como la longitud del Camino Aumentante encontrado por el algoritmo nunca se decrementa. Los caminos encontrados son lo más cortos posibles. El flujo encontrado es igual a la capacidad a travès de corte mínimo en el grafo separando el origen del hundimiento. Hay un solo corte minimal en este grafo, particionando los nodos en los conjuntos ${displaystyle {A,B,C,E}}$ y ${displaystyle {D,F,G}}$, con la capacidad: ${displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5. }$