No algoritmo de Dijkstra para caminhos mínimos, qual estrutura de dado é comumente usada para selecionar…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
No algoritmo de Dijkstra para caminhos mínimos, qual estrutura de dado é comumente usada para selecionar rapidamente o próximo vértice com menor distância estimada?
- A) Uma fila de prioridade, geralmente implementada por um heap (por exemplo, heap binário ou heap de Fibonacci).
- B) Um vetor estático que não permite atualizações rápidas.
- C) Uma pilha, permitindo acesso somente ao último vértice inserido.
- D) Uma lista simples, que armazena todos os vértices em ordem alfabética.
- E) Um hashmap, para armazenar vértices com distâncias fixas.
✅ Resposta correta: alternativa A
Resolução passo a passo
- O algoritmo de Dijkstra, a cada iteração, precisa escolher entre os vértices ainda não finalizados aquele com a menor distância estimada a partir da origem. Depois de escolhido, ele relaxa as arestas que saem desse vértice, o que pode diminuir distâncias de outros vértices.
- Para fazer essa escolha de forma eficiente, usa-se uma fila de prioridade, normalmente implementada com um heap (binário ou de Fibonacci). O heap permite obter o mínimo rapidamente e atualizar (diminuir a chave de) um vértice em tempo logarítmico no caso do heap binário.
- A alternativa B está errada porque um vetor sem organização exigiria varredura linear para achar o mínimo, e a questão pergunta justamente sobre seleção rápida.
- A alternativa C está errada porque uma pilha dá acesso apenas ao último elemento inserido, o que não corresponde ao vértice de menor distância.
- A alternativa D está errada porque uma lista ordenada alfabeticamente ignora as distâncias, que são o critério do algoritmo.
- A alternativa E está errada porque um hashmap oferece busca por chave, mas não ordena nem fornece o mínimo; além disso, as distâncias não são fixas no Dijkstra.
- Conclusão: a alternativa A é a correta e coincide com o gabarito oficial.
💡 Dica: Relacione a seleção repetida do menor valor à estrutura que mantém prioridades.
Alternativa por alternativa
A fila de prioridade permite extrair o vértice de menor distância em tempo logarítmico (ou amortizado melhor), essencial para eficiência de Dijkstra.
Acredita que uma estrutura estática basta para o Dijkstra, sem perceber que encontrar o mínimo em um vetor exige percorrer todos os elementos a cada passo.
Confunde a estrutura de pilha (LIFO) com a necessidade de extrair o elemento de menor valor, supondo que o último vértice inserido seria o próximo a processar.
Supõe que a ordenação dos vértices deve seguir o nome (ordem alfabética) em vez da distância estimada, ignorando o critério central do algoritmo.
Por que engana: Confundir a fila de prioridade com uma pilha ou uma lista simples, ignorando que o algoritmo precisa selecionar eficientemente o vértice de menor distância estimada.
Acredita que o Dijkstra precisa apenas de acesso rápido por chave, e que as distâncias são valores fixos, quando elas são atualizadas durante a execução.
Raio-X da questão
Fila de prioridade em Dijkstra
avaliacao
Noções de grafos e algoritmos · Estruturas de dados básicas
Revise o funcionamento de filas de prioridade e heaps em algoritmos de caminhos mínimos.
Confundir a fila de prioridade com uma pilha ou uma lista simples, ignorando que o algoritmo precisa selecionar eficientemente o vértice de menor distância estimada.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- No algoritmo de Dijkstra para caminhos mínimos em um grafo com pesos não negativos, qual estrutura de dados é usada para…
- Em um algoritmo de Dijkstra implementado para um grafo ponderado com listas de adjacência, qual variável armazena a…
- Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
- Em uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a ordem de…
- Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados abstrata é…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
Todas as questões de Programação - Programação usando grafos e árvores
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog