Bellman Ford

Prévia do material em texto

Algoritmo Dijkstra 
Começando do 1:
L(2) = 2; Path 1-2 | L(3) = 5; Path 1-3 | L(4) = 1; Path 1-4 | L(5) = ∞; Path - | L(6) = ∞; Path –
O custo de 1 para 2, é 2. O custo de 1 para 3, é 3. O custo de 1 para 4, é 1. O custo de 1 para 5 ou 6 é inexistente, pois estamos avaliando os caminhos diretos.
Qual o menor custo? No caso ir por 4, fazendo o caminho 1-4, pois tem custo 1.
Sempre o que tiver menor custo da “iteração atual”, repete-se os valores dele até o final e ele é desconsiderado nas iterações seguintes
A próxima iteração é envolvendo o 4, já que este foi o menor custo anterior. Então tem que verificar se é mais barato fazer o caminho 1-2 ou 1-4-2, assim como 1-3 ou 1-4-3. No caso os cálculos ficam dessa forma:
T {1,4}
(2) = min { L(2) = 2; (custo de 1 para 2) 
 L(4) + w4,2 = 1 + 2 = 3; } (custo de 1 para 4, já calculado anteriormente mais o custo de 4 para 2)
O menor custo para se chegar a 2 é o primeiro, pelo caminho 1-2
(3) = min { L(3) = 5; (custo de 1 para 3) 
 L(4) + w4,3 = 1 + 3 = 4; } (custo de 1 para 4, já calculado anteriormente mais o custo de 4 para 3)
O menor custo para se chegar a 3 é o segundo, pelo caminho 1-4-3
(5) = min { L(5) = ∞; (custo de 1 para 5) 
 L(4) + w4,5 = 1 + 1 = 2; } (custo de 1 para 4, já calculado anteriormente mais o custo de 4 para 5)
O menor custo para se chegar a 5 é o segundo, pelo caminho 1-4-5
(6) = min { L(6) = ∞; (custo de 1 para 6) 
 L(4) + w4,6 = 1 + ∞ = ∞; } (custo de 1 para 4, já calculado anteriormente mais o custo de 4 para 6)
Não existe menor custo para se chegar a 6.
Assim a tabela é preenchida com os menores custos. Pode-se perceber que dois caminhos tem o menor custo, (2) e (5), no caso escolhe-se sempre o primeiro a esquerda, neste caso o (2), então ele será repetido, a partir desta iteração até o final (não se deixe enganar pelo valor da primeira iteração que foi igual, foi um mero acaso). Perceba que nem olhamos por (4) pois já está preenchido, da mesma forma que a partir da próxima iteração não iremos fazer os cálculos para (2) e para (4).
Iteração 3 T {1,4,2}
(3) = min { L(3) = 4; (custo de 1 para 4 para 3) 
 L(2) + w2,3 = 2 + 3 = 5; } (custo de 1 para 2, já calculado anteriormente mais o custo de 2 para 3)
O menor custo para se chegar a 3 é o primeiro, pelo caminho 1-4-3
(5) = min { L(5) =2; (custo de 1 para 4 para 5) 
 L(2) + w2,5 = 2 + ∞ = ∞; } (custo de 1 para 2, já calculado anteriormente mais o custo de 2 para 5)
O menor custo para se chegar a 5 é o primeiro, pelo caminho 1-4-5
(6) = min { L(6) =∞; (custo de 1 para 4 para 6) 
 L(2) + w2,6 = 2 + ∞ = ∞; } (custo de 1 para 2, já calculado anteriormente mais o custo de 2 para 6)
Não existe menor custo para se chegar a 6.
T {1,4,2,5}
(3) = min { L(3) = 4; 
 L(5) + w5,3 = 2 + 1 = 3; }
O menor custo para se chegar a 3 é o segundo, pelo caminho 1-4-5-3
(6) = min { L(6) =∞; 
 L(5) + w5,6 = 2 + 2 = 4; }
O menor custo para se chegar a 6 é o segundo, pelo caminho 1-4-5-6
T {1,4,2,5,3}
(6) = min { L(6) = 4; 
 L(3) + w3,6 = 3 + 5 = 8; }
O menor custo para se chegar a 6 é o primeiro, pelo caminho 1-4-5-6
A linha da última iteração é sempre igual a da penúltima