Uma empresa usa um algoritmo que considera dados de tráfego para escolher rotas. Compare: quando o caminho de…
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
Uma empresa usa um algoritmo que considera dados de tráfego para escolher rotas. Compare: quando o caminho de menor peso (soma dos pesos) é preferível ao caminho com menor número de arestas?
- A) Quando buscamos o caminho com mais vértices para aumentar cobertura.
- B) Sempre que o grafo for direcionado, independentemente dos pesos.
- C) Quando todas as arestas têm peso igual, pois evita cálculos.
- D) Quando arestas representam tempos variados e queremos minimizar tempo total.
- E) Somente em grafos muito grandes, para reduzir a complexidade do algoritmo.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Entenda o problema. Em um grafo com pesos nas arestas, o peso de um caminho é a soma dos pesos de suas arestas. O caminho com menos arestas nem sempre é o de menor custo total, porque uma aresta pode ser muito 'cara' e outras, mais numerosas, podem ser baratas.
- Analise o contexto da questão. Um algoritmo de rotas que considera dados de tráfego usa as arestas como trechos com tempos (ou custos) diferentes. O objetivo é chegar ao destino gastando o mínimo possível.
- Verifique a alternativa D. Quando as arestas representam tempos variados e queremos minimizar o tempo total, o caminho de menor peso (soma dos tempos) é exatamente o que interessa. Um caminho com mais trechos pode ser mais rápido se evitar congestionamentos. Esta é a resposta correta.
- Por que as outras estão erradas. A: buscar mais vértices para cobrir mais áreas não é o objetivo de um algoritmo de menor caminho, que busca eficiência. B: a direção das arestas não elimina a necessidade de considerar os pesos, então a alternativa não se sustenta. C: se todas as arestas têm o mesmo peso, o caminho de menor peso coincide com o de menos arestas, então não há diferença a comparar. E: o tamanho do grafo não define quando o peso deve ser considerado; o critério depende dos dados de custo, não do tamanho.
- Conclusão. O caminho de menor peso é preferível quando os pesos representam grandezas reais diferentes, como tempo de trajeto, e o objetivo é minimizar esse total. Assim, a alternativa D está correta e coincide com o gabarito oficial.
💡 Dica: Considere exemplos práticos de rotas e pesos.
Alternativa por alternativa
O aluno pode confundir o objetivo do algoritmo de rotas com cobertura de vértices, achando que passar por mais pontos é melhor. Não percebe que o problema pede eficiência, não abrangência.
O aluno associa grafo direcionado à necessidade de ignorar pesos, achando que a direção das arestas muda o critério de escolha. Não compreende que direção e peso são características independentes do grafo.
O aluno acredita que, se todas as arestas têm o mesmo peso, o caminho de menor peso é preferível por evitar cálculos. Na verdade, com pesos iguais os dois critérios coincidem, então a comparação perde sentido e não há vantagem em evitar cálculos.
Por que engana: Confundir a minimização do número de arestas com a minimização do peso total, escolhendo caminhos mais curtos em termos de arestas, mas não em peso.
Correto: peso representa custo (ex.: tempo); minimizar soma de pesos reduz o custo total.
O aluno acha que o uso de pesos só se justifica em grafos muito grandes, por reduzir a complexidade. Não percebe que o critério de escolha depende do significado dos pesos (como tempo), e não do tamanho do grafo.
Raio-X da questão
caminhos em grafos
avaliacao
caminhos em grafos · pesos em arestas
Revisar algoritmos de busca em grafos e suas aplicações.
Confundir a minimização do número de arestas com a minimização do peso total, escolhendo caminhos mais curtos em termos de arestas, mas não em peso.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Uma empresa de entregas usa um mapa digital representado por um grafo. Nesse modelo, cada cruzamento é um vértice e cada…
- Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…
- Em um mapa de transporte, cada ligação entre dois locais tem um custo positivo, como tempo ou preço da viagem. Um…
- Qual é a técnica ideal para resolver um problema de roteamento entre cidades usando dados de tráfego?
- Um algoritmo para um drone de entrega precisa calcular a rota de menor tempo em um grafo com pesos positivos nas arestas…
- 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