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]
Referências
Ver também Algoritmo de Bellman-Ford Roteamento em redes
Categoria:Hardware Categoria:Tecnologia da informação Categoria:Algoritmos