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 enhora. El algoritmo fue publicado por primera vez por Yefim Dinitz (cuyo nombre también se transcribe como "EA Dinic", en particular como autor de sus primeros artículos) en 1970 [1] [2] y publicado de forma independiente por Jack Edmonds y Richard Karp en 1972. [3] El algoritmo de Dinic incluye técnicas adicionales que reducen el tiempo de ejecución a. [2]
Algoritmo
El algoritmo es idéntico al algoritmo de Ford-Fulkerson , excepto que se define el orden de búsqueda al encontrar la ruta de aumento . La ruta encontrada debe ser la ruta más corta 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 vez, que cada vez que al menos uno de los los bordes se saturan (un borde que tiene el máximo flujo posible), que la distancia desde el borde saturado a la fuente a lo largo de la ruta de aumento debe ser mayor que la última vez que se saturó, y que la longitud es como máximo . Otra propiedad de este algoritmo es que la longitud de la ruta de aumento más corta aumenta monótonamente. Hay una prueba accesible en Introducción a los algoritmos . [4]
Pseudocódigo
algoritmo EdmondsKarp es de entrada : gráfico (el gráfico [v] debe ser la lista de bordes que salen del vértice v en el gráfico original y sus correspondientes bordes inversos construidos que se utilizan para el flujo de retroceso. Cada borde debe tener una capacidad, flujo, fuente y sumidero como parámetros , así como un puntero al borde inverso.) s (vértice de origen) t (vértice de sumidero) salida : caudal (valor del caudal máximo) flujo: = 0 (Inicializar el flujo a cero) repetir (Ejecutar una búsqueda primero en amplitud (bfs) para encontrar el camino st más corto. Usamos 'pred' para almacenar el borde tomado para llegar a cada vértice, para que podamos recuperar el camino después) q: = cola () q.push (s) pred: = array (graph.length) mientras no está vacío (q) cur: = q.pull () para Edge e en el gráfico [cur] hacer si pred [et] = nulo y et ≠ s y e.cap> e.flow entonces pred [et]: = e q.push (et) si no (pred [t] = nulo) entonces (Encontramos una ruta de aumento. Vea cuánto flujo podemos enviar) df: = ∞ for (e: = pred [t]; e ≠ nulo; e: = pred [es ]) do df: = min (df, e.cap - e.flow) (Y actualizar los bordes por esa cantidad) para (e: = pred [t]; e ≠ null; e: = pred [es]) do e.flow: = e.flow + df e.rev.flow: = e.rev.flow - df flujo: = flujo + df hasta que pred [t] = nulo (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 las parejas escrito en los bordes, es el flujo de corriente, y es la capacidad. La capacidad residual de a es , la capacidad total, menos el caudal que ya se utiliza. Si el flujo neto de a es negativo, contribuye a la capacidad residual.
Capacidad | Camino | Red resultante |
---|---|---|
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 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 conjuntos y , con la capacidad
Notas
- ^ 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 . Doklady. 11 : 1277-1280.
- ^ a b 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.
- ^ Edmonds, Jack ; Karp, Richard M. (1972). "Mejoras teóricas en 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 .
- ^ 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.CS1 maint: varios nombres: lista de autores ( enlace )
Referencias
- Algoritmos y complejidad (consulte las páginas 63–69). https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html