Computação7º anoBNCC EF07CO04Difícil⏱ longo

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

Habilidade BNCC EF07CO04

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

Dificuldade Difícil

Bloom Criar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade multipla

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

caminho mais curto em grafos

📌 Objetivo

avaliacao

🧱 Pré-requisitos

representação de grafos · algoritmos de busca

📚 Reveja

Revisar algoritmos de busca em grafos, como Dijkstra e A*.

⚠️ Erro mais comum

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.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

cotidiano

Questões parecidas com resolução

Todas as questões de Programação - Propriedades de grafos

🔎 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