Algoritmo de Edmonds-Karp

En informática , el algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular el caudal máximo en una red de flujo en el tiempo. El algoritmo fue publicado por primera vez por Yefim Dinitz en 1970, ^{[1] [2]} y publicado de forma independiente por Jack Edmonds y Richard Karp en 1972. ^[3] El algoritmo de Dinitz incluye técnicas adicionales que reducen el tiempo de ejecución a . ^[2]${\displaystyle O(|V||E|^{2})}$ ${\displaystyle O(|V|^{2}|E|)}$

La implementación del algoritmo de Wikibook tiene una página sobre el tema: Edmonds-Karp

El algoritmo es idéntico al algoritmo Ford–Fulkerson , excepto que el orden de búsqueda al encontrar el camino de aumento está definido. El camino encontrado debe ser el camino más corto que tenga capacidad disponible. Esto se puede encontrar mediante una búsqueda en amplitud , donde aplicamos un peso de 1 a cada borde. El tiempo de ejecución de se encuentra mostrando que cada camino de aumento se puede encontrar en el tiempo, que cada vez que al menos uno de los bordes se satura (un borde que tiene el flujo máximo posible), que la distancia desde el borde saturado hasta la fuente a lo largo del camino de aumento debe ser más larga que la última vez que se saturó, y que la longitud es como máximo . Otra propiedad de este algoritmo es que la longitud del camino de aumento más corto aumenta monótonamente. Hay una prueba accesible en Introducción a los algoritmos . ^[4]${\displaystyle O(|V||E|^{2})}$${\displaystyle O(|E|)}$${\estilo de visualización E}$${\estilo de visualización |V|}$

El algoritmo de entrada de EdmondsKarp es : gráfico (graph[v] debe ser la lista de aristas que salen del vértice v en el  gráfico original y sus aristas inversas construidas correspondientes  que se usan para el flujo de retroceso.  Cada arista debe tener una capacidad 'cap', flujo, fuente 's' y sumidero 't'  como parámetros, así como un puntero a la arista inversa 'rev'.) s (vértice de origen) t (vértice sumidero)  salida : caudal (Valor del caudal máximo)  flow := 0 (Inicializa el flujo a cero)  repeat  (Ejecuta una búsqueda en amplitud (bfs) para encontrar la ruta más corta.  Usamos 'pred' para almacenar el borde tomado para llegar a cada vértice,  de modo que podamos recuperar la ruta después) q := queue () q.push(s) pred := matriz (grafo.longitud) mientras  no esté vacío(q) y pred[t] = null cur := q.pop() para Edge e en graph[cur] hacer  si pred[et] = null  y et ≠ s y e.cap > e.flow entonces pred[et] := e q.push(et) si  no (pred[t] = null) entonces  (Encontramos una ruta de aumento.  Veamos cuánto flujo podemos enviar) df := ∞  para (e := pred[t]; e ≠ null; e := pred[es]) hacer df := min (df, e.cap - e.flow) (Y actualizamos los bordes en esa cantidad)  para (e := pred[t]; e ≠ null; e := pred[es]) hacer e.flujo := e.flujo + df e.rev.flujo := e.rev.flujo - df flujo := flujo + df hasta que pred[t] = null (es decir, hasta que no se encuentre ninguna ruta de aumento) flujo de retorno

Dada una red de siete nodos, fuente A, sumidero G y capacidades como se muestra a continuación:

En los pares escritos en los bordes, es el flujo actual y es la capacidad. La capacidad residual de a es , la capacidad total, menos el flujo que ya se utiliza. Si el flujo neto de a es negativo, contribuye a la capacidad residual.${\estilo de visualización f/c}$${\estilo de visualización f}$${\estilo de visualización c}$${\estilo de visualización u}$${\estilo de visualización v}$${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$${\estilo de visualización u}$${\estilo de visualización v}$

Camino	Capacidad	Red resultante
${\displaystyle A,D,E,G}$	${\displaystyle {\begin{aligned}&\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))\\=&\min(3-0,2-0,1-0)\\=&\min(3,2,1)=1\end{aligned}}}$
${\estilo de visualización A,D,F,G}$	${\displaystyle {\begin{aligned}&\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,6-0,9-0)\\=&\min(2,6,9)=2\end{aligned}}}$
${\displaystyle A,B,C,D,F,G}$	${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-0,4-0,1-0,6-2,9-2)\\=&\min(3,4,1,4,7)=1\end{aligned}}}$
${\displaystyle A,B,C,E,D,F,G}$	${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,4-1,2-0,0-(-1),6-3,9-3)\\=&\min(2,3,2,1,3,6)=1\end{aligned}}}$

Observe cómo la longitud de la ruta de aumento encontrada por el algoritmo (en rojo) nunca disminuye. Las rutas encontradas son las más cortas posibles. El flujo encontrado es igual a la capacidad a través del corte mínimo en el gráfico que separa la fuente y el sumidero. Solo hay un corte mínimo en este gráfico, que divide los nodos en los conjuntos y , con la capacidad${\displaystyle \{A,B,C,E\}}$${\displaystyle \{D,F,G\}}$

${\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\ }$

1. Algoritmos y complejidad (ver páginas 63 a 69). https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html