Vetor distância

Cada roteador mantém uma tabela (ou vetor) que fornece a melhor distância conhecida até cada destino; as tabelas são atualizadas através de troca de mensagens com seus roteadores vizinhos.

Pode-se representar essa rede usando um grafo em que os nós correspondem aos roteadores e uma aresta entre v e w existe se os dois roteadores estiverem conectados diretamente por um link. O custo da aresta representa o atraso no link (v,w); o menor caminho é aquele que minimiza o atraso entre uma fonte s e um destino t. Para isso, podemos usar o algoritmo de Bellman-Ford, já que ele utiliza apenas conhecimentos locais dos nós vizinhos - suponha que o nó v mantém seu valor de menor distância a t igual a M[v]; então, para atualizar esse valor, v só precisa obter o valor de M[w] de cada vizinho w e computar min (P(v,w)+M[w]) baseado nas informações obtidas, onde P(v,w) é o atraso do link entre v e w.

Entretanto, esse algoritmo pode ser melhorado de forma que se torna melhor para aplicar a roteadores e, ao mesmo tempo, um algoritmo mais rápido, na prática . Em cada iteração i, cada nó v tinha que entrar em contato com cada vizinho w e "puxar" o novo valor M[w] ("pull-based implementation") . Se um nó w não mudou seu valor, então não há necessidade de v pegar o valor M[w] novamente; porém, pelo algoritmo de Bellman-Ford, não tem como v saber isso e ele "puxará" esse valor de qualquer maneira .

Esse desperdício sugere uma "Push-based implementation", onde o valor é apenas transmitido quando sofre alguma mudança. Ou seja, cada nó w cujo valor da distância é alterado em alguma iteração informa seu novo valor a todos os vizinhos na próxima iteração ; isso permite que os vizinhos atualizem seus valores de acordo com a mudança que w sofreu. Se M[w] não mudou, então os vizinhos de w já tem o seu valor e não há necessidade de informá-los de novo. Essa mudança leva à poupança no tempo que o algoritmo leva para rodar, já que nem todos os valores tem que ser atualizados a cada iteração . Logo, o algoritmo deve terminar mais cedo, se nenhum valor mudar durante uma iteração.

O código em Python seria:

PushBasedShortestPath(G,s,t):  #G é a matriz de adjacência com peso
    n=len(G)                              #infinito em (i,j) quando não tem 
    M=[]                                    #aresta entre os nós i e j
    for node in range(n):
        M.append(float("inf"))
    M[t]=0  
    first=range(n)
    for i in range(1,n,1):
        teste=copy.deepcopy(M)
        for node in range(n):
            aux=map(sum,zip(M,G[node]))
            if M[node]>min(aux):
                for node1 in range(n):
                    for node2 in range(n):
                        M[node1]=min(M[node1],G[node1][node2]+M[node2])
                        if M[node1]>(G[node1][node2]+M[node2]):
                            first[node1]=node2
        print M
        if M==teste:
            break
    return M[s]

Veja Também

• Algoritmo de Bellman-Ford
• Roteamento em redes