Algoritmo de Edmonds-Karp

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En ciencias de la computación y teoría de grafos, el Algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular el el flujo maximal en una red de flujo con complejidad O(V E2). Es asintóticamente más lento que el algoritmo de Push-relabel, que tiene complejidad O(V3), pero es habitualmente más rápido en la práctica para grafos ralos. El algoritmo fue publicado por primera vez por un científico soviético, Yefim (Chaim) Dinic, en 1970,[1] y independientemente por Jack Edmonds and Richard Karp in 1972.[2] El Algoritmo de Dinic incluye técnicas adicionales para reducir la complejidad a O(V2E).

Algoritmo[editar]

El algoritmo es idéntico al algoritmo de Ford-Fulkerson, excepto porque el orden para ir buscando los caminos aumentantes está definido. El camino encontrado debe ser el camino más corto que tiene capacidad disponible. Esto se puede encontrar mediante una búsqueda en anchura, ya que dejamos que los bordes tengan unidad de longitud. La complejidad O(V E2)[3] se fundamenta mostrando que cada camino aumentante puede ser encontrado con O(E), cada vez que al menos uno de los lados E se satura, la distancia desde el lado saturado hasta el origen a travès del camino aumentante deberá ser más largo que la última vez que este estuvo saturado, y ese largo es a lo sumo V. Otra propiedad de este algoritmo es que el largo del camino aumentante más corto se incrementa monotonamente. Hay una prueba accesible en:.[4]

Pseudocódigo[editar]

Para una descripción de más alto nivel ver Algoritmo de Ford-Fulkerson.
algoritmo EdmondsKarp
    entrada:
        C[1..n, 1..n] (matrices de capacidad)
        E[1..n, 1..?] (lista de vecinos)
        s             (origen)
        t             (hundimiento)
    salida:
        f             (valor del flujo maximal)
        F             (Una matrix que da un flujo valido con el máximo valor)
    f := 0 (el flujo inicialmente es cero)
    F := array(1..n, 1..n) (Capacidad del residuo de u a v es C[u,v] - F[u,v])
    forever
        m, P := BFS(C, E, s, t, F)
        if m = 0
            break
        f := f + m
        (Búsqueda usando backtracking y estrictura del flujo)
        v := t
        while v ≠ s
            u := P[v]
            F[u,v] := F[u,v] + m
            F[v,u] := F[v,u] - m
            v := u
    return (f, F)

algoritmo BFS
    entrada:
        C, E, s, t, F
    salida:
        M[t]          (Capacidad del camino encontrado)
        P             (Tabla de padres)
    P := array(1..n)
    for u in 1..n
        P[u] := -1
    P[s] := -2 (asegurarse de que el 'origen' no sea reemplazado) 
    M := array(1..n) (Capacidad del camino encontrado hasta el nodo)
    M[s] := ∞
    Q := queue()
    Q.push(s)
    while Q.size() > 0
        u := Q.pop()
        for v in E[u]
            (Si hay capacidad disponible, y v no fue usado antes en la búsqueda)
            if C[u,v] - F[u,v] > 0 and P[v] = -1
                P[v] := u
                M[v] := min(M[u], C[u,v] - F[u,v])
                if v ≠ t
                    Q.push(v)
                else
                    return M[t], P
    return 0, P

Ejemplo[editar]

Dado un grafo dirigido (network) de 7 nodos, origen A, hundimiento G, y las capacidades que se muestran debajo:

Edmonds-Karp flow example 0.svg

En los pares f/c escritos en los lados , f es el flujo actual, y c es la capacidad. La capacidad de la resta entre u y v es c_f(u,v)=c(u,v)-f(u,v), la capacidad total, menos el flujo que esta en uso. Si el flujo desde u a v es negativo, esto contribuye a la capacidad del residuo.

Capacidad Camino
Network resultante
\min(c_f(A,D),c_f(D,E),c_f(E,G)) =

\min(3-0,2-0,1-0) =
\min(3,2,1) = 1

A,D,E,G
Edmonds-Karp flow example 1.svg
\min(c_f(A,D),c_f(D,F),c_f(F,G)) =

\min(3-1,6-0,9-0) =
\min(2,6,9) = 2

A,D,F,G
Edmonds-Karp flow example 2.svg
\min(c_f(A,B),c_f(B,C),c_f(C,D),c_f(D,F),c_f(F,G)) =

\min(3-0,4-0,1-0,6-2,9-2) =
\min(3,4,1,4,7) = 1

A,B,C,D,F,G
Edmonds-Karp flow example 3.svg
\min(c_f(A,B),c_f(B,C),c_f(C,E),c_f(E,D),c_f(D,F),c_f(F,G)) =

\min(3-1,4-1,2-0,0--1,6-3,9-3) =
\min(2,3,2,1,3,6) = 1

A,B,C,E,D,F,G
Edmonds-Karp flow example 4.svg

Notar como la longitud del Camino Aumentante encontrado por el algoritmo nunca se decrementa. Los caminos encontrados son lo más cortos posibles. El flujo encontrado es igual a la capacidad a travès de corte mínimo en el grafo separando el origen del hundimiento. Hay un solo corte minimal en este grafo, particionando los nodos en los conjuntos \{A,B,C,E\} y \{D,F,G\}, con la capacidad: c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\

Referencias[editar]

  1. E. A. Dinic (1970). «Algorithm for solution of a problem of maximum flow in a network with power estimation». Soviet Math. Doklady (Doklady) 11:  pp. 1277–1280. 
  2. Jack Edmonds and Richard M. Karp (1972). «Theoretical improvements in algorithmic efficiency for network flow problems». Journal of the ACM 19 (2):  pp. 248–264. doi:10.1145/321694.321699. http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/08/Edmonds72.pdf. 
  3. Penazzi, Daniel. «Complejidad de Edmonds-Karp». Consultado el 27 de abril de 2012.
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein (2001). «26.2». Introduction to Algorithms (second edición). MIT Press and McGraw–Hill. pp. 660–663. ISBN 0-262-53196-8. 

Enlaces externos[editar]