Bellman-Ford

Equações de Bellman

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

Algoritmo distribuído e assíncrono de Bellman-Ford

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.