Um algoritmo para um drone de entrega precisa calcular a rota de menor tempo em um grafo com pesos positivos…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Um algoritmo para um drone de entrega precisa calcular a rota de menor tempo em um grafo com pesos positivos nas arestas (tempo de voo). Qual algoritmo é mais adequado para rastrear o caminho mínimo a partir da base do drone?
- A) Dijkstra
- B) Busca em largura (BFS)
- C) A* (A-estrela)
- D) Floyd–Warshall
- E) Bellman-Ford
✅ Resposta correta: alternativa A
Resolução passo a passo
- A questão pede um algoritmo de caminho mínimo a partir de uma única origem (a base do drone), em um grafo com pesos positivos (tempos de voo), e que permita rastrear o caminho encontrado. Passo 2: O algoritmo de Dijkstra resolve exatamente esse problema: a partir da origem, ele calcula a menor distância até todos os demais vértices, guardando para cada vértice o seu predecessor, o que permite reconstruir a rota completa. Passo 3: Ele exige pesos não negativos, condição que o enunciado garante ao informar que os pesos são positivos. Passo 4: Por que as outras estão erradas: a BFS minimiza o número de arestas, não a soma dos tempos, então ignora os pesos; o A* exige uma heurística admissível e é voltado a um destino específico, sendo uma extensão e não a resposta mais geral; o Floyd–Warshall calcula caminhos entre todos os pares de vértices, o que é desnecessário e mais custoso para uma única origem; o Bellman-Ford funciona também com pesos negativos, mas é mais lento e a questão destaca pesos positivos, tornando o Dijkstra a escolha mais adequada. Passo 5: Conclusão: o gabarito oficial A (Dijkstra) está correto. Passo 6: Dúvida registrada: o A* poderia ser útil em uma aplicação prática com destino fixo e heurística de distância, mas o enunciado pede o algoritmo mais adequado de forma geral para o caminho mínimo a partir da base.
💡 Dica: Considere os algoritmos de busca de caminho mínimo.
Alternativa por alternativa
Dijkstra encontra caminhos mínimos em grafos com pesos não negativos de forma eficiente.
Acredita que a busca em largura encontra o caminho de menor tempo, pois ela acha o caminho com menos passos. Não percebe que, com pesos diferentes nas arestas, o menor número de arestas não corresponde ao menor tempo total.
Supõe que o A* é sempre a versão mais avançada e, por isso, a melhor opção para qualquer caminho mínimo. Não percebe que ele depende de uma heurística admissível e de um destino específico, enquanto o problema pede a rota a partir da base.
Por que engana: Confundir o algoritmo de Dijkstra com o algoritmo de Floyd-Warshall, que é usado para encontrar caminhos mínimos entre todos os pares de vértices, não apenas a partir de um único ponto.
Acha que, por calcular todos os caminhos mínimos entre todos os pares de vértices, o Floyd–Warshall seria o mais completo e, portanto, o mais adequado. Não considera que a questão trata de uma única origem e que essa abordagem é desnecessariamente custosa.
Escolhe o Bellman-Ford por ser um algoritmo geral que aceita pesos negativos. Ignora a informação do enunciado de que os pesos são positivos, o que torna o Dijkstra mais eficiente para o caso descrito.
Raio-X da questão
caminho mínimo em grafos
avaliacao
caminho mínimo em grafos · algoritmos de busca
Revisar algoritmos de busca de caminho mínimo em grafos.
Confundir o algoritmo de Dijkstra com o algoritmo de Floyd-Warshall, que é usado para encontrar caminhos mínimos entre todos os pares de vértices, não apenas a partir de um único ponto.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em períodos de calor intenso, o comitê de saúde de uma escola pretende divulgar, antes do recreio, um boletim na rádio…
- Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica…
- — O alerta saiu de Arumã, mas o enlace entre Caju e Ema parou de funcionar — avisou a operadora da central fluvial…
- Por que duas oficinas muito procuradas não podem ocorrer no mesmo horário? Em uma situação fictícia, a organização de…
- — Se eu voltar pelo mesmo corredor, chego de novo na entrada? — perguntou uma visitante ao testar o aplicativo de um…
- Ontem o mapa do festival me mandou dar uma volta enorme reclamou uma visitante. Para reduzir aglomeracoes, a…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog