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

• No algoritmo de Dijkstra para caminhos mínimos em um grafo com pesos não negativos, qual estrutura de dados é usada para…
• No algoritmo de Dijkstra para caminhos mínimos, qual estrutura de dado é comumente usada para selecionar rapidamente o…
• Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
• Ao representar um grafo ponderado com listas de adjacência, qual tipo de variável deve armazenar o peso de cada aresta e…
• Elabore um algoritmo em pseudocódigo que, dado um grafo representado por lista de adjacência e dois vértices (origem…
• Para que o algoritmo de Dijkstra retorne corretamente caminhos mínimos em um grafo (dirigido ou não) com pesos nas…

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.