Em um algoritmo de Dijkstra implementado para um grafo ponderado com listas de adjacência, qual variável…

Questão

Em um algoritmo de Dijkstra implementado para um grafo ponderado com listas de adjacência, qual variável armazena a menor distância conhecida de cada vértice à fonte?

1. A) Uma variável booleana que indica se um nó foi visitado.
2. B) O vetor 'dist' (ou 'distância'), que contém a melhor estimativa de distância do vértice fonte a cada vértice.
3. C) Uma lista encadeada ordenada, que permite acesso aleatório aos nós da árvore.
4. D) Uma fila (queue), pois facilita a exploração de todos os nós antes de finalizar os atuais.
5. E) Um array estático, onde os índices representam diretamente os nós da árvore.

✅ Resposta correta: alternativa B

Resolução passo a passo

1. No algoritmo de Dijkstra, cada vértice precisa guardar a melhor estimativa de distância até a fonte, que é atualizada durante a execução. Essa informação fica normalmente em um vetor (array) chamado 'dist' ou 'distância', com uma posição para cada vértice.
2. Inicialmente, dist[fonte] recebe 0 e os demais vértices recebem infinito. Ao examinar uma aresta do vértice u até o vértice v com peso p, se dist[u] + p for menor que dist[v], o valor de dist[v] é atualizado. Assim, ao final, dist[v] contém a menor distância encontrada da fonte até v.
3. Por que as outras alternativas estão erradas:
4. A) Uma variável booleana apenas indica se o nó já foi visitado ou finalizado; ela não guarda nenhuma distância.
5. C) Uma lista encadeada ordenada não é a estrutura que guarda a distância de cada vértice e não oferece acesso aleatório eficiente.
6. D) Uma fila é a estrutura de uma busca em largura, não armazena distâncias por vértice no Dijkstra.
7. E) Um array estático com índices representando nós descreve uma forma de representar nós, mas não é a variável que armazena a menor distância conhecida; o array 'dist' é que cumpre esse papel.
8. Conclusão: a resposta correta é a alternativa B, que coincide com o gabarito oficial.

💡 Dica: Lembre-se da estrutura de dados utilizada no algoritmo de Dijkstra.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
• Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
• Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
• Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
• Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
• — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.