Algoritmo de Edmonds-Karp

Algoritmo de Edmonds-Karp

El algoritmo de Edmonds-Karp tiene un tiempo de ejecución de O(VE²), es más rápido que el algoritmo de Ford-Fulkerson para gráficos densos, es decir, un grafico que contiene un gran número de aristas (o arcos) dependiendo del número de vértices.

El algoritmo de Edmonds-Karp es idéntico al algoritmo de Ford-Fulkerson, excepto por el orden de búsqueda utilizado para determinar una ruta creciente. El camino encontrado debe ser el camino más corto que tenga una capacidad positiva. Tal camino puede ser encontrado por un campo de ancho, suponiendo que todos los arcos tienen longitud unitaria. Tenga en cuenta que la longitud de la ruta creciente aumenta con cada iteración.
Código de Wikipedia
algoritmo EdmondsKarp
    aporte: C [1..n, 1..n] (matriz de capacidad)
        E [1..n, 1 ..?] (listas de vecinos)
        s             (fuente)
        t             (pozos)
    producción: f             (valor de caudal máximo)
        F             (matriz que da un flujo válido de valor máximo)
    f: = 0 (el flujo inicial es cero)
    F: = formación(1..n, 1..n) (la capacidad residual de u a v es C[u,v] - F[u,v])
    para siempre
        m, P: = AmplitudPrimera búsqueda (C, E, s, t, F)
        tejo m = 0
            pausa
        f: = f + m
        (Retroceda y observe el flujo)
        v: = t
        tiempo v ≠ s u: = P [v] F [u, v]: = F [u, v] + m F [v, u]: = F [v, u] - m v: = u
    regreso (f, F)
algoritmo AmplitudPrimeroBuscar
    aporte: Es f
    producción: M [t]          (capacidad del camino encontrado)
        PAG             (mesa de padres)
    P: = formación(1..n)
    por tu en 1..n P [u]: = -1 P [s]: = -2 (para asegurarse de que no se redescubra la fuente) 
    M: = formación(1..n) (capacidad de la ruta encontrada al nodo)
    M [s]: = ∞ Q: = cola () Q.push (s)
    tiempo Q.size ()> 0 u: = Q.pop ()
        por v en UE]
            tejo C [u, v] - F [u, v]> 0 y P [v] = -1 P [v]: = u M [v]: = min (M [u], C [u, v] - F [u, v])
                tejo v ≠ t Q. empujar (v)
                demás
                    regreso M [t], P
    regreso 0, P

algoritmo de edmonds-karp flujo máximo problema de flujo máximo gráfico de desviación de corte mínimo flujo creciente

Compartir, repartir