Ir para o conteúdo
Warrior

Grafos

Mensagens Recomendadas

SamLapin    0
SamLapin

Sorry... Estava a olhar para outra figura.

Sim tens razão... Eu consigo perceber isso mas o algoritmo não me dá esse caminho.

Corrige-me se estiver errado mas o algoritmo é:

- Começar no vértice fonte;

- Relaxar os adjacentes

- Escolher o que tiver custo menor e daí por diante até chegar ao vértice pretendido

Certo?

Deve haver algo que não estou a entender bem :S

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Sim, é isso. Vou fazer esse exemplo, há algum passo do algoritmo que não estás a fazer bem (apesar de, aparentemente, o teres percebido).

Vértices =    {  A , B , C ,  D , E ,  F ,  G , H }

Distancias = { oo, oo, oo, oo, oo, oo, oo, oo }  // oo = infinito

Começa-se em G

Vértices =    {  A , B , C ,  D , E ,  F ,  G , H }

Distancias = { oo, oo, oo, oo, oo, oo,  0 , oo }

Relaxar A, E, H

Vértices =    {  A , B ,  C ,  D , E ,  F , G ,  H  }

Distancias = {  5 , oo, oo, oo, 10, oo,  0 , 12 }

O vértice com distância menor que ainda não foi processado é o A (5) . Relaxar B (5+3) e C (5+2).

Vértices =    {  A , B ,  C , D , E ,  F ,  G ,  H  }

Distancias = {  5 , 8 ,  7 , oo, 10, oo,  0 , 12 }

O vértice com distância menor que ainda não foi processado é o C (7) . Relaxar E, mas de C para E o custo era 10, igual ao que já estava, por isso ignora.

A seguir, o vértice a processar é o B com distancia 8. Relaxa E (8+1) e D (8+8)

Vértices =    {  A , B ,  C , D , E ,  F ,  G ,  H  }

Distancias = {  5 , 8 ,  7 , 16, 9 , oo,  0 , 12  }

Processa E (9). Relaxa F (9+4) e H (9+1)

Vértices =    {  A , B ,  C , D , E ,  F ,  G ,  H  }

Distancias = {  5 , 8 ,  7 , 16, 9 , 13,  0 , 10  }

Processa H (10). Relaxa F (10+2)

Vértices =    {  A , B ,  C , D , E ,  F ,  G ,  H  }

Distancias = {  5 , 8 ,  7 , 16, 9 , 12,  0 , 10  }

Processa F (12). Relaxa D (12+2)

Vértices =    {  A , B ,  C , D , E ,  F ,  G ,  H  }

Distancias = {  5 , 8 ,  7 , 14, 9 , 12,  0 , 10  }

Processa D. É o destino. A distância é 14

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
SamLapin    0
SamLapin

Basicamente processaste os vértices todos. A diferença está naqueles em que incluis depois no caminho.

Pelo que eu percebi da tua execução, quando estamos a processar um vértice, quando relaxamos os adjacentes, se a distância dele aos seus adjacentes não se alterou então ignoramos?

Quando estavas a processar o C viste que a distância dele ao E não se alterava no processo de relaxação e então voltaste para o B.

EDIT: I think I got it...

Tem a ver com o predecessor. Tu ignoraste porque o predecessor dele não passou a ser o vertice que estavas a processar. Logo deixa de ser uma hipótese.

Obrigado pela ajuda :(

Mais uns valorzinhos no teste de amanha

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Sim, única coisa que é ignorada é o update da distância ao vértice e o correspondente predecessor.

Porque o método é sempre o mesmo: procurar qual é o vértice que ainda não foi processado com distância mínima.

Se não existisse a ligação G->E (10), no C ias colocar a distancia a E a 10, com predecessor C. No entanto, tens de processar o B antes do E porque o B tem distância 8 (e nesse processo vais actualizar a distancia de E para 9)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
SamLapin    0
SamLapin

O caminho, no final, é dado, por exemplo, por uma lista ligada (com inserção no inicio) começando pelo vértice destino e inserindo os predecessores até à fonte :(

Obrigado pela ajuda. ;)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade