Jump to content
alligator

Explicacao do algoritmo Dijkstra ?

Recommended Posts

alligator

Boas

Preciso de um pequena ajuda para o resolver o seguinte problema . 

Preciso de fazer uma implementação do algoritmo dijkstra.  Ja tenho o grafo criado , ou seja tenho o grafo e as respectivas distancias ( ligações entre nós do grafo ).

Precisava do algoritmo dijsktra adequado para correr nesta situação ! Como faço a implementação deste ? Alguém ja trabalhou com este algoritmo ?

#define P (dist[v] + t->wt)
void Dijkstra(Graph G, int s, int pred[], double wt[]) {   // O que é o int pred[] e o double wt[] ?
int v, w; link t;
PQinit();
for (v = 0; v < G->V; v++) {
pred[v] = -1; 
dist[v] = maxWT;     // O que é o dist[v] e o maxWt ?
PQinsert(v); } 
dist[s] = 0.0;
PQdec(s);
while (!PQempty())
if (dist[v = PQdelmin()] != maxWT) 
for (t = G->adj[v]; t != NULL; t = t->next)   // O que é o adj[v] ? 
if (P < dist[w = t->v]) 
{ dist[w] = P; PQdec(w); pred[w] = v; } 
}

Foi me facultado o anterior código , contudo ha variáveis e estruturas que não entendo o significado . Ficaria ntaum agradecido se alguém me fizesse a explicação do mesmo de forma a eu conseguir avançar no trabalho .

O meu grafo foi criado a medida que  extrai informacão do ficheiro ! Sera que me falta alguma coisa ?

Obrigado pela atenção

Share this post


Link to post
Share on other sites
gangsterveggies

Para perceberes o algoritmo tens aqui uma visualização case-study do algoritmo:

https://www.youtube.com/embed/8Ls1RqHCOPw?feature=oembed

.

Uma implementação muito boa está neste livro: http://online-judge.uva.es/problemset/Art_of_Programming_Contest_SE_for_uva.pdf, vê a página 164.

Também podes ver outro tópico daqui do forum: http://www.portugal-a-programar.pt/index.php?showtopic=36564.

Já agora, esta é uma questão que devia ser posta na secção de Algoritmia e Lógica e não em C...


--

GangsterVeggies - DCC/FCUP

Share this post


Link to post
Share on other sites
alligator

Obrigado , pela ajuda !

Relativamente ao algoritmo do livro que me recomendaste , ja consegui perceber melhor o seu funcionamento ! Seria bom era ver um programa com o seu funcionamento d acordo com o material do livro ( array de precedentes , funções de filas prioritárias ... ) . Seria possível postarem aqui uma implementação ?

obrigado

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.