Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma…

Questão

Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada aresta representa uma estrada direta e o número associado a cada aresta indica o tempo estimado de viagem, em minutos. Todos os tempos são positivos. Para orientar ambulâncias, o sistema precisa encontrar, entre uma cidade de origem e uma cidade de destino, o percurso cujo tempo total de viagem seja o menor possível. Com base nessa representação e nas características dos dados, qual abordagem permite determinar corretamente o percurso de menor tempo entre duas cidades?

1. A) Aplicar busca em profundidade, seguindo o primeiro percurso encontrado.
2. B) Aplicar busca em largura, considerando iguais os custos de todas as estradas.
3. C) Aplicar o algoritmo de Dijkstra, considerando os tempos positivos das estradas.
4. D) Usar uma matriz de adjacência, armazenando os tempos das estradas.
5. E) Escolher sempre a estrada com menor tempo no ponto atual.

✅ Resposta correta: alternativa C

Resolução passo a passo

1. O problema pede o caminho de menor soma de pesos (tempos) entre uma origem e um destino em um grafo com pesos positivos nas arestas.
2. Busca em profundidade percorre o grafo seguindo um caminho até o fim antes de voltar, sem considerar pesos; o primeiro caminho encontrado não é necessariamente o de menor tempo, então a alternativa A está errada.
3. Busca em largura encontra o caminho com menor número de arestas, o que só coincide com o menor tempo se todas as estradas tiverem o mesmo tempo; como os tempos variam, a alternativa B está errada.
4. O algoritmo de Dijkstra é feito para caminhos mínimos em grafos com pesos não negativos; como todos os tempos são positivos, ele garante o resultado correto, sendo a alternativa C a correta.
5. Uma matriz de adjacência é apenas uma forma de representar o grafo; ela não determina por si só o percurso mínimo, então a alternativa D está errada.
6. Escolher sempre a estrada mais rápida a partir do ponto atual é a heurística gulosa, que pode levar a um caminho total maior ao evitar uma estrada inicial lenta que leva a um trajeto final muito mais rápido; por isso a alternativa E está errada.
7. Conclusão: a alternativa C está correta e coincide com o gabarito oficial.

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

Alternativa por alternativa

Raio-X da questão

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…
• Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
• Qual é a técnica ideal para resolver um problema de roteamento entre cidades usando dados de tráfego?
• Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem)…
• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
• Considere um problema que envolve a otimização de rotas entre várias cidades. Qual estrutura é mais eficiente para…

Todas as questões de Programação - Programação usando grafos e árvores