Algoritmo de Edmonds-Karp

En ciencias de la computación , el algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular el flujo máximo en una red de flujo en${\displaystyle O(|V||E|^{2})}$tiempo. El algoritmo fue publicado por primera vez por Yefim Dinitz en 1970, ^{[ 1 ] [ 2 ]} y publicado independientemente 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${\displaystyle O(|V|^{2}|E|)}$. ^{[ 2 ]}

El algoritmo es idéntico al algoritmo de Ford-Fulkerson , excepto que se define el orden de búsqueda al encontrar el camino de aumento . El camino encontrado debe ser el camino más corto que tenga capacidad disponible. Esto se puede encontrar mediante una búsqueda en anchura , donde aplicamos un peso de 1 a cada arista. El tiempo de ejecución de${\displaystyle O(|V||E|^{2})}$se encuentra demostrando que cada camino de aumento se puede encontrar en${\displaystyle O(|E|)}$tiempo, que cada vez que al menos uno de los bordes E se satura (un borde que tiene el flujo máximo posible), que la distancia desde el borde saturado hasta la fuente a lo largo de la trayectoria de aumento debe ser mayor que la última vez que se saturó, y que la longitud es como máximo${\displaystyle |V|}$Otra propiedad de este algoritmo es que la longitud del camino de aumento más corto aumenta monótonamente. ^{[ 4 ]} Un esquema de demostración que utiliza estas propiedades es el siguiente:

La demostración establece primero que la distancia del camino más corto desde el nodo fuente s a cualquier nodo que no sea sumidero v en una red de flujo residual aumenta monótonamente después de cada iteración de aumento (Lema 1, demostrado a continuación). Luego, muestra que cada uno de los${\displaystyle |E|}$Los bordes pueden ser críticos en la mayoría de los casos.${\displaystyle {\frac {|V|}{2}}}$veces durante la duración del algoritmo, lo que proporciona un límite superior de${\displaystyle O\left({\frac {|V||E|}{2}}\right)=O(|V||E|)}$aumentando las iteraciones. Dado que cada iteración toma${\displaystyle O(|E|)}$ tiempo (limitado por el tiempo para encontrar el camino más corto usando la búsqueda en anchura), el tiempo total de ejecución de Edmonds-Karp es${\displaystyle O(|V||E|^{2})}$según sea necesario. ^{[ 4 ]}

Para demostrar el Lema 1, se puede utilizar la demostración por contradicción asumiendo que existe una iteración de aumento que provoca que la distancia del camino más corto de s a v disminuya . Sea f el flujo antes de dicho aumento y${\displaystyle f'}$Sea el flujo posterior. Denotemos la distancia mínima en una red de flujo residual .${\displaystyle G_{f}}$desde nodos${\displaystyle u,v}$como${\displaystyle \delta _ {f}(u,v)}$Se puede derivar una contradicción demostrando que${\displaystyle \delta _ {f}(s,v)\leq \delta _ {f'}(s,v)}$, lo que significa que la distancia del camino más corto entre el nodo fuente s y el nodo no sumidero v no disminuyó de hecho. ^{[ 4 ]}

El algoritmo EdmondsKarp es la entrada : grafo (graph[v] debe ser la lista de aristas que salen del vértice v en el grafo original y sus correspondientes aristas inversas construidas que se utilizan para el flujo de retroceso. Cada arista debe tener una capacidad 'cap', flujo, origen 's' y destino 't' como parámetros, así como un puntero a la arista inversa 'rev'). s (Vértice de origen) t (Vértice de destino) salida : caudal (valor del caudal máximo) flujo := 0 (Inicializa el flujo a cero) repetir (Ejecuta una búsqueda en anchura (bfs) para encontrar el camino st más corto. Usamos 'pred' para almacenar la arista tomada para llegar a cada vértice, de modo que podamos recuperar el camino posteriormente) q := cola () q.push(s) pred := array (graph.length) mientras no esté vacío(q) y pred[t] = null cur := q.pop() para cada arista 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 las aristas por esa cantidad) para (e := pred[t]; e ≠ null; e := pred[es]) hacer flujo.e := flujo.e + df flujo de e.rev. := flujo de e.rev. - df flujo := flujo + df hasta que pred[t] = null (es decir, hasta que no se encontró ninguna ruta de aumento) flujo de retorno

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

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

Observe cómo la longitud del camino de aumento encontrado por el algoritmo (en rojo) nunca disminuye. Los caminos encontrados son los más cortos posibles. El flujo encontrado es igual a la capacidad a través del corte mínimo en el grafo que separa la fuente y el sumidero. Solo hay un corte mínimo en este grafo, que divide 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.\ }$

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