Em uma competição de programação, uma equipe precisa calcular o menor custo para sair de um ponto inicial e…

Questão

Em uma competição de programação, uma equipe precisa calcular o menor custo para sair de um ponto inicial e chegar a cada outro ponto de uma rede. Cada ligação da rede tem um valor numérico não negativo, que representa seu custo. A equipe considera usar Dijkstra, busca em largura, busca em profundidade, Prim ou Kruskal. Qual algoritmo é mais apropriado para encontrar os menores caminhos a partir de um ponto inicial nessa rede com custos não negativos?

1. A) Busca em largura
2. B) Algoritmo de Kruskal
3. C) Busca em profundidade
4. D) Algoritmo de Dijkstra
5. E) Algoritmo de Prim

✅ Resposta correta: alternativa D

Resolução passo a passo

1. O problema pede os menores caminhos a partir de um ponto inicial (origem única) para todos os outros pontos, em uma rede com custos não negativos nas ligações.
2. Esse é o problema clássico de caminhos mínimos de fonte única, para o qual o algoritmo de Dijkstra é a escolha padrão quando os pesos são não negativos. Ele mantém uma estimativa de distância para cada vértice e, a cada passo, fixa o vértice não visitado de menor distância, relaxando suas arestas.
3. A alternativa A (busca em largura) só encontra caminhos mínimos quando todas as ligações têm o mesmo custo; com custos diferentes ela não garante o menor custo total.
4. A alternativa B (Kruskal) constrói uma árvore geradora de custo mínimo, que conecta todos os pontos com custo total mínimo, mas não calcula o menor caminho de um ponto inicial até cada outro.
5. A alternativa C (busca em profundidade) percorre a rede explorando um caminho até o fim antes de voltar, sem qualquer critério de custo, portanto não serve para menores caminhos.
6. A alternativa E (Prim) também gera uma árvore geradora mínima; ela minimiza o custo total da árvore, e não a soma do caminho de um ponto inicial até cada destino.
7. Logo, a alternativa correta é a D, Algoritmo de Dijkstra, que coincide com o gabarito oficial.

💡 Dica: Considere os algoritmos de busca em grafos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Para organizar uma exposição escolar, a turma desenhou as ligações diretas entre quatro setores. Cada letra indica um…
• Técnicos instalam uma rede de comunicação por cabos entre os postos de uma reserva ambiental. Os postos são Riacho…
• Moradores acompanham a criação de um aplicativo para orientar deslocamentos durante a feira do bairro. No mapa…
• Durante os preparativos para uma feira de ciências no bairro, a organização desenhou um mapa digital dos caminhos…
• Por que uma rede de aviso precisa continuar funcionando mesmo quando um ponto para de operar? Em uma cidade litorânea, a…
• — Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta…

Todas as questões de Programação - Propriedades de grafos