Computação6º anoBNCC EF06CO06Média⏱ longo

Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF06CO06

Comparar diferentes casos particulares (instâncias) de um mesmo problema, identificando as semelhanças e diferenças entre eles, e criar um algoritmo para resolver todos, fazendo uso de variáveis (parâmetros) para permitir o tratamento de todos os casos de forma genérica.

Fonte: Base Nacional Comum Curricular (MEC).

Questão

Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa representado por grafos. Explique como as variáveis e as arestas devem ser definidas para que o algoritmo funcione corretamente.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Um algoritmo como Dijkstra pode ser utilizado para encontrar o caminho mais curto. As variáveis devem incluir a lista de cidades (nós) e as distâncias entre elas (arestas). É importante garantir que as arestas sejam ponderadas corretamente, representando a distância real entre as cidades. O algoritmo deve percorrer todos os nós, calculando a distância acumulada até o nó de destino, escolhendo sempre a menor distância até encontrar o caminho mais curto.

Explicação

O algoritmo de Dijkstra é eficaz para encontrar o caminho mais curto em grafos, pois utiliza uma abordagem sistemática que garante a exploração de todos os nós de forma otimizada. A definição adequada das variáveis, como cidades e distâncias, é crucial para que o algoritmo funcione, permitindo que as arestas reflitam corretamente as relações entre os nós. Ao priorizar as menores distâncias acumuladas, o algoritmo assegura que o caminho mais curto seja encontrado de maneira eficiente.

Raio-X da questão

Dificuldade Média

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

algoritmo de caminho mais curto

📌 Objetivo

avaliacao

🧱 Pré-requisitos

representação de grafos · algoritmos de busca

📚 Reveja

Revisar conceitos de grafos e algoritmos de busca.

⚠️ Erro mais comum

O aluno pode descrever um algoritmo que não considera corretamente as arestas ou as variáveis necessárias para calcular o caminho mais curto.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

cientifico

Questões parecidas com resolução

Todas as questões de Estratégias de solução de problemas - Generalização

🔎 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