search

iagoac / mc202

Disciplina MC202 - Estruturas de Dados
GNU General Public License v3.0
17 stars 13 forks source link

Dúvida sobre retorno da função Dijkstra e sobre o Heap usado #121

Closed leo-leao closed 4 years ago

leo-leao commented 4 years ago

Boa noite, tudo bem? Estou com dúvida com relação ao retorno da função Dijkstra, que retorna um ponteiro pai com dados, vocês sabem me dizer especificamente o que eu tenho nesse vetor pai, se for o caminho como identificar o fim do caminho na hora de printar os dados na tela? Outra duvida é com relação ao Heap utilizado, ele é um heap de mínimo ou de máximo?

iagoac commented 4 years ago

Estou com dúvida com relação ao retorno da função Dijkstra, que retorna um ponteiro pai com dados, vocês sabem me dizer especificamente o que eu tenho nesse vetor pai, se for o caminho como identificar o fim do caminho na hora de printar os dados na tela?

Depende muito de como é feita sua implementação do Dijkstra. Normalmente, ele retorna os antecessores de cada vértice no caminho mais curto.

Outra duvida é com relação ao Heap utilizado, ele é um heap de mínimo ou de máximo?

Heap mínimo. Você está indo pra uma das implementações mais complexas que existem deste algoritmo. Esta só perde pra Heap de Fibonacci

leo-leao commented 4 years ago

Existe alguma implementação mais simples? Eu implemente com matrizes de adjacencias mas tive problemas com tempo no Susy nos testes fechados, então o Enoque me aconselhou a utilizar fila de prioridades. No caso eu estou tentando replicar a função Dijkstra apresentada na aula Grafos (Algoritmos)