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 um mapa de transporte, cada ligação entre dois locais tem um custo positivo, como tempo ou preço da viagem. Um…
- Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…
- Uma empresa de entregas usa um mapa digital representado por um grafo. Nesse modelo, cada cruzamento é um vértice e cada…
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
- Em uma competição de programação, uma equipe precisa calcular o menor custo para sair de um ponto inicial e chegar a…
- Uma empresa de transporte de cargas deseja otimizar suas rotas. Ao analisar os dados de entrega, perceberam que 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