Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FCM 2018
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq337488
Banca
FCM
Órgão
IFN-MG
Ano
2018
Nível
Superior
Cargo
Ciências da Computação: Teoria da Computação
Tendo como entrada um grafo acíclico dirigido ponderado G = (V, E), pode-se calcular o caminho mínimo de origem única,
Aaplicando a busca em largura em G, o caminho mínimo de origem única é calculado em tempo θ(V² ).
Baplicando a busca em largura no grafo transposto GT = (V, ET ), o caminho mínimo de origem única é calculado em tempo θ(V² ).
Crelaxando as arestas de G de acordo com a ordenação topológica de seus vértices, o caminho mínimo de origem única é calculado em tempo θ(V + E).
Daplicando a busca em profundidade no grafo transposto GT = (V, ET ), o caminho mínimo de origem única é calculado em tempo θ(V + E).
Erelaxando as arestas pela busca em profundidade no grafo de entrada G = (V, E) e, posteriormente, aplicando a busca em profundidade no grafo transposto GT = (V, ET ), o caminho mínimo de origem única é calculado em tempo θ(V² ).
Revelar gabarito e comentário▾
GabaritoC — relaxando as arestas de G de acordo com a ordenação topológica de seus vértices, o caminho mínimo de origem única é calculado em tempo θ(V + E).
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Caminho mínimo em DAG – Algoritmo com ordenação topológica
Gabarito: letra C. Em um grafo acíclico dirigido (DAG), o caminho mínimo de origem única pode ser calculado relaxando as arestas na ordem topológica dos vértices, com complexidade θ(V+E). As demais alternativas propõem abordagens incorretas (busca em largura ou profundidade) ou tempos de execução equivocados.
A questão testa o conhecimento do algoritmo específico para grafos acíclicos dirigidos ponderados. Diferente do algoritmo de Dijkstra (que exige pesos não negativos) ou de Bellman-Ford (que lida com ciclos negativos), um DAG permite uma solução mais eficiente usando ordenação topológica.
1Ordenação topológica (DFS)
2Inicializar distâncias (∞, fonte=0)
3Para cada vértice na ordem topológica
4Relaxar todas as arestas (u, v)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
A busca em largura (BFS) calcula caminho mínimo apenas para grafos não ponderados (peso unitário). Em um grafo ponderado, BFS não considera os pesos, portanto não encontra o caminho mínimo. Além disso, a complexidade θ(V²) não é típica para BFS (que é O(V+E) com lista de adjacência).
Alternativa B — ❌ Incorreta
A busca em largura no grafo transposto também não resolve o problema. O transposto inverte as arestas, mas BFS continua ignorando pesos. Complexidade θ(V²) novamente inadequada.
Alternativa C — ✅ Correta ⟵ GABARITO
O algoritmo clássico para caminho mínimo em DAG consiste em:
Obter a ordenação topológica dos vértices (por DFS, tempo O(V+E)).
Inicializar distâncias (∞, exceto fonte = 0).
Para cada vértice u na ordem topológica, relaxar todas as arestas (u, v).
Como não há ciclos, ao processar u, sua distância já está correta (pois todos os caminhos para u vêm de vértices anteriores na ordenação). O relaxamento de cada aresta ocorre uma vez, resultando em θ(V+E).
Alternativa D — ❌ Incorreta
Busca em profundidade (DFS) não calcula caminho mínimo. Embora a DFS seja usada para obter a ordenação topológica, a simples aplicação dela no grafo transposto não produz caminhos mínimos. Complexidade θ(V+E) é correta para DFS, mas o método não resolve o problema.
Alternativa E — ❌ Incorreta
A descrição “relaxar arestas pela busca em profundidade” é vaga e incorreta. Não existe algoritmo conhecido que relaxe arestas durante a DFS e depois aplique DFS no transposto para obter caminho mínimo em DAG. A complexidade θ(V²) também não condiz.
PEGA ESSA DICA!
Em provas de algoritmos, lembre-se da tríade de caminho mínimo:
DAG: ordenação topológica + relaxamento → θ(V+E)
Pesos não negativos: Dijkstra → O((V+E) log V)
Pesos negativos (sem ciclos negativos alcançáveis): Bellman-Ford → O(V·E)