Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
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
Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de viagem entre locais, calcule o caminho de menor tempo entre um nó origem e um nó destino. Descreva variáveis, estrutura de dados (por exemplo, fila de prioridade) e analise a complexidade do algoritmo.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Variáveis: dist[ ], prev[ ], visitados; estrutura: fila de prioridade (min-heap) que ordena por dist. Inicialização: para todo vértice v, dist[v] ? 8; prev[v] ? nulo; dist[origem] ? 0; inserir (origem,0) no min-heap. Enquanto min-heap não vazio: (u, d_u) ? extrair mínimo do heap se u == destino: interrompa (caminho encontrado) se d_u > dist[u]: continue para cada aresta (u ? v) com peso w: alt ? dist[u] + w se alt < dist[v]: dist[v] ? alt prev[v] ? u inserir ou diminuir-chave (v, alt) no heap Ao fim: reconstruir caminho seguindo prev[] de destino até origem; dist[destino] é o tempo mínimo. Justificativa e complexidade: Este é o algoritmo de Dijkstra usando um min-heap; garante caminho de menor tempo para pesos não negativos. Operações de extração e diminuição-chave dominam o custo; com heap binário a complexidade é O((V+E) log V), e com heap de Fibonacci O(V log V + E). Variáveis prev permitem reconstruir o caminho; dist guarda as estimativas provisórias de tempo.
Explicação
O algoritmo descrito utiliza o método de Dijkstra, que é apropriado para encontrar o caminho de menor custo em grafos com arestas de pesos não negativos. A estrutura de dados escolhida, o min-heap, permite otimizar a extração do vértice com a menor distância atualizada, garantindo eficiência nas operações. A análise de complexidade apresentada demonstra que o algoritmo é escalável e eficiente, lidando adequadamente com a quantidade de vértices e arestas do grafo.
Raio-X da questão
caminho de menor tempo
avaliacao
algoritmos de busca · grafos ponderados
Revisar algoritmos de busca em grafos e suas complexidades.
O aluno pode confundir a estrutura de dados necessária, optando por uma lista simples em vez de uma fila de prioridade, o que compromete a eficiência do algoritmo.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
- Em um grafo ponderado onde cada aresta tem duas informações: capacidade (número máximo de veículos) e custo…
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são pontos de…
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…
- Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem)…
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
🔎 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