Computação2º anoBNCC EF15CO02Média⏱ longo

Desenvolva um algoritmo que encontre o caminho mais curto em um grafo representando uma rede de computadores…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF15CO02

Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.

Fonte: Base Nacional Comum Curricular (MEC).

Questão

Desenvolva um algoritmo que encontre o caminho mais curto em um grafo representando uma rede de computadores. Descreva os passos principais e explique como ele resolve o problema.

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

Resposta esperada

Um algoritmo que resolve o problema de caminho mais curto, como o algoritmo de Dijkstra, deve seguir os seguintes passos: 1) Inicializar as distâncias dos vértices; 2) Colocar o vértice inicial na fila de prioridade; 3) Enquanto a fila não estiver vazia, remover o vértice com a menor distância; 4) Para cada vizinho, calcular a distância total e atualizar se menor; 5) Repetir até o final. Esse algoritmo garante que o menor caminho é encontrado de maneira eficiente usando uma estrutura de dados adequada como uma fila de prioridade.

Explicação

O algoritmo de Dijkstra é eficaz para encontrar o caminho mais curto em grafos, pois utiliza uma abordagem sistemática que explora os vértices em ordem de distância mínima. A utilização de uma fila de prioridade permite que o algoritmo selecione rapidamente o próximo vértice a ser processado, garantindo eficiência. Além disso, a atualização das distâncias dos vizinhos assegura que o algoritmo sempre considere as rotas mais curtas disponíveis.

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

caminho mais curto em grafos

📌 Objetivo

avaliacao

🧱 Pré-requisitos

algoritmos de busca · representação de grafos

📚 Reveja

Revisar algoritmos de busca em grafos, como Dijkstra e Bellman-Ford.

⚠️ Erro mais comum

O aluno pode confundir a lógica de busca em profundidade com a busca em largura, resultando em um algoritmo que não encontra o caminho mais curto.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

cientifico

Questões parecidas com resolução

Todas as questões de Algoritmos

🔎 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