No algoritmo de Dijkstra para caminhos mínimos em um grafo com pesos não negativos, qual estrutura de dados é…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Reconhecer objetos do mundo real e digital que podem ser representados através de grafos que estabelecem uma organização com uma quantidade variável de vértices conectados por arestas, fazendo manipulações simples sobre estas representações.
Fonte: Base Nacional Comum Curricular (MEC).Questão
No algoritmo de Dijkstra para caminhos mínimos em um grafo com pesos não negativos, qual estrutura de dados é usada para selecionar eficientemente o próximo vértice com menor distância conhecida?
- A) Uma árvore de expansão mínima do grafo.
- B) Uma fila de prioridade (por exemplo, um heap) para operações de extração do menor.
- C) Um conjunto de todos os caminhos possíveis no grafo.
- D) Uma lista simples de todos os vértices.
- E) Um vetor onde cada posição representa o estado de cada vértice.
✅ Resposta correta: alternativa B
Resolução passo a passo
- O algoritmo de Dijkstra mantém, para cada vértice, uma estimativa da menor distância conhecida até a origem. A cada iteração, ele precisa escolher rapidamente o vértice ainda não processado com menor estimativa.
- Para fazer essa escolha de forma eficiente, usa-se uma fila de prioridade (por exemplo, um heap binário ou de Fibonacci), que permite inserir vértices, atualizar prioridades e extrair o mínimo em tempo logarítmico (no heap binário).
- Por que a alternativa A está errada: a árvore de expansão mínima é um conceito de outro problema (algoritmos de Prim e Kruskal) e não corresponde ao caminho mínimo de uma origem.
- Por que a alternativa C está errada: armazenar todos os caminhos possíveis é inviável, pois o número de caminhos cresce muito rapidamente, e o Dijkstra não faz isso.
- Por que a alternativa D está errada: uma lista simples obrigaria a varrer todos os vértices a cada iteração para achar o mínimo, tornando o algoritmo menos eficiente.
- Por que a alternativa E está errada: um vetor de estados indica apenas se cada vértice foi visitado ou não, mas não permite selecionar o menor valor de distância de forma eficiente sem uma busca linear.
- Conclusão: a resposta correta é a B, coincidente com o gabarito oficial.
💡 Dica: Lembre-se das estruturas de dados utilizadas em algoritmos de grafos.
Alternativa por alternativa
O aluno confunde o problema de caminhos mínimos com o de árvore geradora mínima, associando a palavra 'mínimo' à árvore de expansão mínima.
Por que engana: Confundir a fila de prioridade com uma lista simples, acreditando que a lista é mais eficiente para selecionar o próximo vértice.
Dijkstra precisa repetidamente obter o vértice de menor distância já descoberta; uma fila de prioridade permite extrair e atualizar chaves eficientemente.
O aluno imagina que o Dijkstra precisa considerar todos os caminhos possíveis para escolher o melhor, ignorando que o algoritmo guarda apenas uma distância por vértice.
O aluno acredita que basta guardar os vértices em uma lista e procurar o menor valor, sem perceber que essa busca linear a cada passo torna o método ineficiente.
O aluno entende que marcar o estado de cada vértice (visitado ou não) já resolve a seleção do próximo vértice, sem perceber que é preciso comparar as distâncias para achar o menor.
Raio-X da questão
algoritmo de Dijkstra
avaliacao
estruturas de dados · algoritmos de grafos
Revisar estruturas de dados utilizadas em algoritmos de grafos.
Confundir a fila de prioridade com uma lista simples, acreditando que a lista é mais eficiente para selecionar o próximo vértice.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- No algoritmo de Dijkstra para caminhos mínimos, qual estrutura de dado é comumente usada para selecionar rapidamente o…
- 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) é…
- Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados abstrata é…
- Em uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a ordem de…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
🔎 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