Algoritmo de Edmonds-Karp

Algoritmo para calcular el caudal máximo en una red de flujo

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|)}$

Algoritmo

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|)}$ ${\displaystyle E}$ ${\displaystyle |V|}$

Pseudocódigo

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

Ejemplo

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. ${\displaystyle f/c}$ ${\displaystyle f}$ ${\displaystyle c}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$

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.\ }$

Notas

1. Dinic, EA (1970). "Algoritmo para la solución de un problema de caudal máximo en una red con estimación de potencia". Matemáticas soviéticas - Doklady . 11 . Doklady: 1277–1280.
2. Yefim Dinitz (2006). "El algoritmo de Dinitz: la versión original y la versión de Even" (PDF) . En Oded Goldreich ; Arnold L. Rosenberg; Alan L. Selman (eds.). Ciencias de la computación teórica: ensayos en memoria de Shimon Even . Springer. págs. 218–240. ISBN. 978-3-540-32880-3.
3. Edmonds, Jack ; Karp, Richard M. (1972). "Mejoras teóricas en la eficiencia algorítmica para problemas de flujo de red" (PDF) . Revista de la ACM . 19 (2): 248–264. doi :10.1145/321694.321699. S2CID  6375478.
4. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2009). "26,2". Introducción a los algoritmos (tercera ed.). Prensa del MIT. págs. 727–730. ISBN 978-0-262-03384-8.{{cite book}}: CS1 maint: multiple names: authors list (link)

Referencias

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