Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo representando uma cidade. Explique as etapas e a lógica por trás da escolha desse algoritmo.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Um algoritmo amplamente utilizado para encontrar o caminho mais curto em grafos é o algoritmo de Dijkstra. Ele começa atribuindo a cada nó um valor infinito e, em seguida, define o valor do nó inicial como zero. O algoritmo então explora todos os vizinhos do nó atual, acumulando os custos e atualizando os valores dos nós, até que todos os nós tenham sido explorados. A lógica é garantir que sempre se escolha o caminho com o menor custo acumulado até o destino.
Explicação
O algoritmo de Dijkstra é eficaz para encontrar o caminho mais curto em grafos ponderados, pois utiliza uma abordagem gulosa que prioriza a exploração dos caminhos com menor custo acumulado. Ao atualizar continuamente os valores dos nós, ele garante que a solução final seja a mais otimizada. Além disso, sua estrutura permite uma implementação eficiente, especialmente em grafos densos.
Raio-X da questão
caminho mais curto em grafos
avaliacao
representação de grafos · algoritmos de busca
Revisar algoritmos de busca em grafos, como Dijkstra e A*.
O aluno pode descrever um algoritmo que não é eficiente para encontrar o caminho mais curto, como o algoritmo de busca em profundidade, que não garante a solução ótima.
ciencia_tecnologia
pensamento_critico
cotidiano
Questões parecidas com resolução
- Para organizar uma exposição escolar, a turma desenhou as ligações diretas entre quatro setores. Cada letra indica um…
- Técnicos instalam uma rede de comunicação por cabos entre os postos de uma reserva ambiental. Os postos são Riacho…
- Moradores acompanham a criação de um aplicativo para orientar deslocamentos durante a feira do bairro. No mapa…
- Durante os preparativos para uma feira de ciências no bairro, a organização desenhou um mapa digital dos caminhos…
- Por que uma rede de aviso precisa continuar funcionando mesmo quando um ponto para de operar? Em uma cidade litorânea, a…
- — Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta…
🔎 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