Algoritmo de Edmonds-Karp

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 (cuyo nombre también se transcribe como "EA Dinic", notablemente 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] $O(|V||E|^{2})$ $O(|V|^{2}|E|)$

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 anchura , donde aplicamos un peso de 1 a cada borde. El tiempo de ejecución de se encuentra mostrando que cada ruta 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 de la ruta de aumento debe ser más larga que la última vez que se saturó, y que la longitud es como máximo $O(|V||E|^{2})$ ${\ estilo de visualización O (| E |)}$ ${\ estilo de visualización E}$ ${\ estilo de visualización | V |}$ . 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]

En los pares escritos en los bordes, está el flujo de corriente y está 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. ${\ 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}$ $c_{f}(u,v)=c(u,v)-f(u,v)$ ${\ estilo de visualización u}$ ${\ estilo de visualización v}$