Dijkstra - Implementação em lista de listas;

[lesiano]

Boas;

Implementei o algoritmo de Dijstra e fiz há mão e... devo estar a pensar mal.

Imaginem um grafo com as cidades "Porto", "Braga", "Guarda" e "Fafe".

Ligações:

Porto: c/Braga por 10 e c/Guarda por 10;

Braga: c/Porto por 10 e c/Fafe por 5;

Fafe: c/Braga por 5;

Guarda: c/Porto por 10;

Qual é o custo mínimo de Guarda a Fafe? A mim dá-me 5 no papel e no algoritmo, mas escrevendo o grafo são 25.  ?

Onde é q estou a pensar mal?

Thx!

[Triton]

O código?

[pedrosorio]

http://img147.imageshack.us/img147/5601/grafo.th.jpg

O que é que queres dizer com "no papel dá 5"? Quer dizer que quando tu segues o teu código te dá 5 e é o mesmo que se compilares? É evidente que estás a implementar mal o algoritmo não é? (código?++)

[lesiano]

O código ñ podia postar pq isto é para um trabalho e cópias dão direito a q o trabalho fique anulado.

Já vi o q estava a fazer mal.

Na actualização dos custos dos vértices adjacentes, eu estava smp a fazer:

if(((verticeorigem->onus) + (primeira->custo)) < (vertice_testado->onus))

{

vertice_testado->onus = (verticeorigem->onus) + (primeira->custo);

vertice_testado->pai = verticeorigem;

}

}

Mesmo nos adjacentes dos adjacentes. Claro que nesses, o código será:

if(((vertice_minimo->onus) + (primeira->custo)) < (vertice_testado->onus))

{

vertice_testado->onus = (vertice_minimo->onus) + (primeira->custo);

vertice_testado->pai = vertice_minimo;

}

Uma nova dúvida q eu até sei resolver mas quero saber se é de facto a melhor forma:

No final do algoritmo, ele retorna-me o grafo com os onus actualizados, isto é, eu quero ir de Guarda a Fafe e ele actualiza o grafo com a origem Guarda. O grafo é retornado com os valores em cada cidade q correspondem ao mínimo para ir da Guarda lá. Depois tenho uma função q procura a cidade destino, no caso Fafe, no grafo e peço:

cidade_encontrada -> onus;

A minha dúvida é saber como construir o caminho. Cada vértice tem o seu pai, imposto pelo algoritmo. Eu pelo pai consigo saber o anterior, logo, estava a pensar fazer qq coisa como:

(Pseudo-codigo)

Ir de "cidade_origem" a "cidade_destino" tem um custo de "cidade_encontrada -> onus", e passa por:

- Função q lista cidades por onde passa:

print "cidade_origem"

noactual = cidade_origem->pai;

while(noactual->pai!=NULL)

{

print noactual->nome

noactual = noactual->pai->pai

}

"pai" é um apontador para a cidade pai da anterior.

Thx.