Algoritmo de Edmonds-Karp

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 flujo maximal en una red de flujo(i.e. computer network) con complejidad O(V E²). Es asintóticamente más lento que el algoritmo de Push-relabel, que tiene complejidad O(V³), 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] e independientemente por Jack Edmonds y Richard Karp en 1972.^[2] El Algoritmo de Dinic incluye técnicas adicionales para reducir la complejidad a O(V²E).

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 E²)^[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:

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 está en uso. Si el flujo desde $u$ a $v$ es negativo, esto contribuye a la capacidad del residuo.

Capacidad	Camino
Capacidad	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$

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

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

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

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