Em um mapa de transporte, cada ligação entre dois locais tem um custo positivo, como tempo ou preço da viagem…

Questão

Em um mapa de transporte, cada ligação entre dois locais tem um custo positivo, como tempo ou preço da viagem. Um aplicativo precisa encontrar o caminho entre dois locais cujo custo total seja o menor possível. Qual algoritmo é mais adequado para encontrar o caminho de menor custo total entre dois locais nesse mapa?

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

✅ Resposta correta: alternativa B

Resolução passo a passo

1. O problema pede o caminho entre dois locais de um mapa em que todas as ligações têm custo positivo, e o objetivo é que a soma dos custos seja mínima.
2. Esse é o problema clássico de caminho mínimo entre um par de vértices em um grafo com pesos não negativos (aqui, pesos positivos).
3. O algoritmo de Dijkstra foi projetado exatamente para isso: parte da origem, atualiza sucessivamente a menor distância conhecida até cada vértice e garante a solução ótima quando não há pesos negativos.
4. Por que as outras estão erradas: o Kruskal (A) e o Prim (E) constroem árvores geradoras mínimas, que conectam todos os vértices com custo total mínimo, mas não garantem o menor caminho entre dois locais específicos; a busca em largura (C) encontra o caminho com menor número de ligações, ignorando os custos; e a busca em profundidade (D) não otimiza custo algum, apenas percorre o grafo.
5. Conclusão: a alternativa correta é a B, Algoritmo de Dijkstra, que coincide com o gabarito oficial.

💡 Dica: Considere as principais abordagens de busca em grafos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…
• Em uma competição de programação, uma equipe precisa calcular o menor custo para sair de um ponto inicial e chegar a…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
• 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…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…

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.