Algoritmo de Edmonds-Karp

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

En informática , el algoritmo de Edmonds-Karp es una implementación del método Ford-Fulkerson para calcular el flujo 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 de Ford-Fulkerson , excepto que se define el orden de búsqueda al encontrar la ruta aumentada . El camino encontrado debe ser un 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 máximo flujo posible), que la distancia desde el borde saturado hasta la fuente a lo largo del camino de aumento debe ser más largo que la última vez que se saturó, y que la longitud sea como máximo . Otra propiedad de este algoritmo es que la longitud del camino de aumento más corto aumenta de forma monótona. 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

Se  introduce el algoritmo EdmondsKarp : gráfico (gráfico [v] debe ser la lista de aristas que salen del vértice v en el  gráfico original y sus correspondientes aristas inversas construidas  que se utilizan para el flujo de retroceso.  Cada arista debe tener una capacidad 'cap', flow, source ' s' y sumidero 't'  como parámetros, así como un puntero al borde inverso 'rev'.) Salida s ( vértice de origen) t (vértice de sumidero) : caudal (Valor del caudal máximo)  flujo: = 0 (Inicializar el flujo a cero)  repetir  (Ejecutar una búsqueda en amplitud (bfs) para encontrar la ruta st más corta.  Usamos 'pred' para almacenar el borde tomado para llegar a cada vértice,  para que podamos recuperar la ruta después) q := cola () q.push(s) pred := matriz (graph.length) mientras  no esté vacío (q) y pred[t] = null cur := q.pop() para Edge e en el gráfico [cur], haga  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.  Vea cuánto flujo podemos enviar) df := ∞  for (e := pred[t]; e ≠ null; e := pred[es ]) do df := min (df, e.cap - e.flow) (Y actualice los bordes en esa cantidad)  for (e := pred[t]; e ≠ null; e := pred[es]) do e.flujo := e.flujo + df e.rev.flujo := e.rev.flujo - df flujo := flujo + df hasta pred[t] = null (es decir, hasta que no se encuentre una 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, está el flujo de corriente y es la capacidad. La capacidad residual de a es la capacidad total, menos el flujo que ya se utiliza. Si el flujo neto desde 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. Los caminos encontrados son los más cortos posibles. El caudal encontrado es igual a la capacidad a través del corte mínimo en el gráfico que separa la fuente y el sumidero. Sólo hay un corte mínimo en este gráfico, dividiendo 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 solución de un problema de caudal máximo en una red con estimación de potencia". Matemáticas soviéticas - Doklady . Doklady. 11 : 1277-1280.
2. Yefim Dinitz (2006). "Algoritmo de Dinitz: la versión original y la versión de Even" (PDF) . En Oded Goldreich ; Arnold L. Rosenberg; Alan L. Selman (eds.). Informática teórica: ensayos en memoria de Shimon Even . Saltador. 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 (véanse las páginas 63 a 69). https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html