Na escola, cada caminho até a biblioteca tem uma distância em quilômetros. Qual algoritmo encontra o caminho…

Questão

Na escola, cada caminho até a biblioteca tem uma distância em quilômetros. Qual algoritmo encontra o caminho mais curto?

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

✅ Resposta correta: alternativa B

Resolução passo a passo

1. O enunciado pede o algoritmo que encontra o caminho mais curto em um grafo em que cada caminho (aresta) tem uma distância em quilômetros, ou seja, um grafo com pesos positivos.
2. O algoritmo de Dijkstra foi projetado exatamente para isso: a partir de um vértice de origem, calcula a menor distância até todos os demais vértices, escolhendo sempre o vértice ainda não processado com menor distância acumulada e atualizando os vizinhos. Assim, a alternativa B está correta, e coincide com o gabarito oficial.
3. A busca em largura (A) encontra o caminho com menor número de arestas, mas ignora os pesos; só serviria para o caminho mais curto se todas as distâncias fossem iguais.
4. O algoritmo de Prim (C) gera uma árvore geradora mínima, que conecta todos os vértices com custo total mínimo, mas não garante o menor caminho entre dois pontos específicos.
5. A busca em profundidade (D) percorre o grafo explorando um ramo até o fim antes de voltar, sem qualquer preocupação com distâncias, por isso não encontra o caminho mais curto.
6. O algoritmo de Kruskal (E) também constrói uma árvore geradora mínima, selecionando arestas de menor peso sem ciclos, e não resolve o problema do caminho mais curto entre dois pontos.

💡 Dica: Considere os algoritmos de busca de caminho mais curto.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Ao projetar um algoritmo para calcular o caminho mais curto entre salas em um mapa da escola, qual representação de…
• Durante uma aula, os alunos precisam descobrir o menor caminho entre duas salas em uma escola, representadas por um…
• Desenvolva um algoritmo que encontre o caminho mais curto em um grafo representando uma rede de computadores. Descreva…
• Você deve criar um algoritmo para encontrar o caminho mais curto em um grafo que representa uma rede de computadores…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
• Em um mapa de transporte, cada ligação entre dois locais tem um custo positivo, como tempo ou preço da viagem. Um…

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.