Desenvolva um algoritmo em pseudocódigo que, dado um grafo conectado com pesos não negativos e um vértice…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Utilizar conceitos iniciais de uma linguagem de programação na implementação de algoritmos escritos em linguagem corrente e/ou matemática.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Desenvolva um algoritmo em pseudocódigo que, dado um grafo conectado com pesos não negativos e um vértice origem, calcule as distâncias mínimas a todos os outros vértices; descreva as estruturas de dados usadas, a complexidade assintótica e como os resultados devem ser organizados em uma tabela de frequências de distâncias.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Pseudocódigo (Dijkstra): 1. Inicialize dist[v]=8 para todo v; dist[origem]=0. Use fila de prioridade (min-heap) que armazena pares (dist,v). 2. Inserir (0,origem) em heap. 3. Enquanto heap não vazio: extrair (d,u); se d>dist[u] continuar; para cada aresta (u,w,peso): se dist[w]>dist[u]+peso então dist[w]=dist[u]+peso; atualizar/inserir (dist[w],w) no heap. Estruturas: array dist[ ], boolean visitado opcional, min-heap para extrair menor distância. Complexidade: O((V+E) log V) com heap binário; com heap de Fibonacci O(E+V log V). Tabela de frequências: enumerar valores finitos de dist[ ] (arredondar se necessário), agrupar por valor ou por intervalos, contar ocorrências e apresentar colunas: distância | frequência | percentual. Tratar vértices inalcançáveis separadamente (dist = 8). Exemplo de saída: 0:1, 2.5:3, 5:2, 8:0.
Explicação
O pseudocódigo apresentado utiliza o algoritmo de Dijkstra, que é apropriado para encontrar distâncias mínimas em grafos com pesos não negativos. As estruturas de dados, como o array para distâncias e a fila de prioridade, garantem eficiência na atualização e extração das distâncias mínimas. A tabela de frequências organiza os resultados de forma clara, permitindo a visualização das distâncias e suas ocorrências, além de tratar vértices inalcançáveis de maneira adequada.
Raio-X da questão
algoritmo de grafos
avaliacao
algoritmo de grafos · pseudocódigo
Revisar algoritmos de busca em grafos e suas complexidades.
O aluno pode confundir a implementação do algoritmo com a descrição das estruturas de dados, não abordando a complexidade assintótica corretamente.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resoluçã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