Algoritmo de Edmonds-Karp

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Broom icon.svg
As referências deste artigo necessitam de formatação (desde janeiro de 2014). Por favor, utilize fontes apropriadas contendo referência ao título, autor, data e fonte de publicação do trabalho para que o artigo permaneça verificável no futuro.

Na Ciência da computação e teoria dos grafos, o Algoritmo de Edmonds-Karp é uma implementação do Algoritmo de Ford-Fulkerson para a resolução do problema de fluxo máximo em uma rede de fluxo. A característica que o distingue é que o caminho de aumento mais curto é usado em cada iteração, o que garante que o calculo vai terminar. Na maioria das implementações, o caminho de aumento mais curto é encontrado usando uma busca em largura, a qual roda em um tempo de . Isto é assintoticamente mais lento que algoritmo remarcagem-para-frente, o qual roda em , mas é freqüentemente mais rápido para utilização em grafos esparsos. O algoritmo foi publicado pela primeira vez pelo cientista russo Dinic, em 1970, e depois, de forma independente, por Edmonds e Karp que o publicaram em 1972. O algoritmo de Dinic inclui técnicas adicionais para reduzir o tempo para a ordem de .

Algoritmo[editar | editar código-fonte]

Este algoritmo é idêntico ao Algoritmo de Ford-Fulkerson, exceto que a ordem de busca quando encontra que o caminho de aumento de fluxo definido. O caminho encontrado deve ser o caminho mais curto com capacidade disponível.

Exemplo de implementação[editar | editar código-fonte]

Implementação Python:

def edmonds_karp(C, source, sink):
    n = len(C) # C is the capacity matrix
    F = [[0] * n for _ in xrange(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]

    while True:
        path = bfs(C, F, source, sink)
        if not path:
            break
        # traverse path to find smallest capacity
        u,v = path[0], path[1]
        flow = C[u][v] - F[u][v]
        for i in xrange(len(path) - 2):
            u,v = path[i+1], path[i+2]
            flow = min(flow, C[u][v] - F[u][v])
        # traverse path to update flow
        for i in range(len(path) - 1):
            u,v = path[i], path[i+1]
            F[u][v] += flow
            F[v][u] -= flow
    return sum([F[source][i] for i in xrange(n)])

def bfs(C, F, source, sink):
    P = [-1] * len(C) # parent in search tree
    P[source] = source
    queue = [source]
    while queue:
        u = queue.pop(0)
        for v in xrange(len(C)):
            if C[u][v] - F[u][v] > 0 and P[v] == -1:
                P[v] = u
                queue.append(v)
                if v == sink:
                    path = []
                    while True:
                        path.insert(0, v)
                        if v == source:
                            break
                        v = P[v]
                    return path
    return None

Exemplo[editar | editar código-fonte]

Dada uma rede de sete nós e capacidade como mostrado abaixo:

Ek-flow 0.png

No pares escritos nos arcos, é o fluxo actual, e é a capacidade. A capacidade residual de para é , a capacidade total, menos a vazão que já esta sendo usada. Se o fluxo da rede de para é negativo, isto contribui para capacidade residual.

Caminho Capacidade Rede resultante




Ek-flow 1.png




Ek-flow 2.png




Ek-flow 3.png




Ek-flow 4.png

Note como o comprimento do caminho aumentante encontrado pelo algoritmo nunca diminui. Os caminhos encontrados são os mais curtos possíveis. O fluxo encontrado é igual a capacidade que cruza o menor corte no grafo separando a fonte e o consumo. Há somente um corte mínimo neste grafo, particionando-se os nodos nos conjuntos e , com a capacidade .

Referências[editar | editar código-fonte]

  • E. A. Dinic, Algorithm for solution of a problem of maximum flow in a network with power estimation, Soviet Math. Doklady, Vol 11 (1970) pp1277-1280.
  • J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM, Vol 19, No. 2 (1972) pp248-264. PDF (necessita autenticação)