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

• Em um mapa de transporte, cada ligação entre dois locais tem um custo positivo, como tempo ou preço da viagem. Um…
• Num mapa de ruas de uma cidade (grafo com arestas não negativas), para encontrar o menor caminho entre dois pontos, qual…
• Um algoritmo para um drone de entrega precisa calcular a rota de menor tempo em um grafo com pesos positivos nas arestas…
• Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…
• Você deve criar um algoritmo para encontrar o caminho mais curto em um grafo que representa uma rede de computadores…
• Desenvolva um algoritmo que encontre o caminho mais curto em um grafo representando uma rede de computadores. Descreva…

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