Bellman-Ford
Last updated
Last updated
Quando o custo das ligações não é negativo.
Custo da ligação de um nó X para o nó que se segue no caminho mais curto para A. |
+ |
Caminho mais curto desse nó para A |
= |
Caminho mais curto e X para A |
Cada nó transmite, periodicamente, para todos os seus vizinhos, a estimativa do custo entre si mesmo e um nó destino R.
Ao receber essa mensagem, cada nó vai também calcular a sua estimativa entre si próprio e o nó R.
Adiciona ao valor recebido, o valor da sua estimativa do custo entre ele e o vizinho que enviou a mensagem.
Escolhem-se os vizinhos que tiverem menor custo entre si.
