Algoritmo de Bellman-Ford

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um dígrafo ponderado, ou seja, cujas arestas têm peso, inclusive negativo. O Algoritmo de Dijkstra resolve o mesmo problema, em um tempo menor, porém exige que todas as arestas tenham pesos positivos. Portanto, o algoritmo de Bellman-Ford é normalmente usado apenas quando existem arestas de peso negativo.[1]

O algoritmo de Bellman-Ford executa em tempo O(v \times a) onde v é o número de vértices e a o número de arestas.[2] [3]

Este algoritmo, obviamente, só funciona assumindo que o grafo não tem ciclo negativo, pois se houvesse, não haveria caminho mínimo, basta ficar iterando neste próprio ciclo. Para encontrar o algoritmo, comece Comece denotando por M[i,v] o custo mínimo para irmos do nó v até o nó t usando no máximo i arestas. Agora, veja que, como o grafo não tem ciclo negativo, M[i,v]=M[n-1,v] (para todo i>=n-1), pois tendo n arestas no caminho, há algum ciclo nele, mas sabemos que todo ciclo tem peso positivo, então poderíamos reduzir o caminho diminuindo o custo, logo, os caminhos ideias terão no máximo n-1 arestas.

Veja que há uma recorrência simples para M[i,v], pois se o caminho ideal tem no máximo i-1 arestas, a resposta será M[i-1,v], caso contrário (se ele tiver exatamente i arestas), chame de (v,w) a primeira aresta, M[i,v] será igual a o valor do peso da aresta (v,w)+M[i-1,w], assim, temos uma fórmula para M[i,v] em função dos termos anteriores, sendo ela:

M[i,v]=min(M[i-1,v],min(M[i-1,w]+P(v,w))(em w pertencente aos nós do grafo)). Mas sabemos os casos iniciais, pois  M[0,v] é infinito para todo v nos nós do grafo, exceto o nó t, que é o nó que o objetivo é chegar, onde M[0,t]=0. Com esta recorrência, fica óbvio um pseudocódigo para implementar este algoritmo, como foi implementado, este código tem complexidade O(n^3).

Há uma simplificação óbvia nesta implementação, pois procuramos o mínimo em todos os nós do grafo, mas basta procurar nos nós que v chega, reduzindo a complexidade para O(n*arestas). O que reduz significativamente a complexidade do algoritmo caso o mesmo tenha poucas arestas. Podemos também otimizar o espaço usado para implementar o algoritmo, basta que a cada etapa, não salvemos M[i,v] para todo v, mas que atualizemos M a cada etapa, precisando apenas de uma lista, e não uma lista de listas para resolver o problema, o algoritmo fica bem parecido, mudando apenas a recorrência para: M[v] = min(M[v],min(M[w]+P(v,w)) (em w pertencente aos nós do grafo que v chega)).

def devolveaux(G):  #G é a matriz de adjacência
    n=len(G)
    auxG=copy.deepcopy(G)
    ind=[]
    for i in range(n):
        ind.append([])
    for i in range(n):
        for j in range(n):
            if G[i][j]!=float("inf"):
                ind[i].append(j)
    for i in range(n):
        while sum(auxG[i])==float("inf"):
            auxG[i].remove(float("inf"))                
    return [auxG,ind]
 
def improvedshortestpath(G,s,t):
    n=len(G)
    M=[]
    auxM=[]
    for node in range(n):
        M.append(float("inf"))
    M[t]=0
    [auxG,ind]=devolveaux(G)       
    for i in range(1,n,1):
        for node in range(n):
            auxM=[]
            for j in range(len(ind[node])):
                    auxM.append(M[ind[node][j]])
            aux=map(sum,zip(auxM,auxG[node]))
            if aux!=[]:           
                M[node]=min(M[node],min(aux))
    return M[s]

Ver também[editar | editar código-fonte]

Referências

  1. Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8, S. 585-586.
  2. https://tools.ietf.org/html/rfc1058
  3. http://algs4.cs.princeton.edu/44sp/
Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Ligações externas[editar | editar código-fonte]