Vetor distância
Este artigo não cita fontes confiáveis. (Maio de 2015) |
Esta página ou seção carece de contexto. |
Esta página ou seção foi marcada para revisão devido a incoerências ou dados de confiabilidade duvidosa. |
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]