Gabarito C
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.
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !