Questão 2876674

• Banca: FCM
• Órgão: IFN-MG
• Ano: 2018
• Provas: FCM - 2018 - IFN-MG - Ciências da Computação: Teoria da Computação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Grafos

Tendo como entrada um grafo acíclico dirigido ponderado G = (V, E), pode-se calcular o caminho mínimo de origem única,

• A. aplicando a busca em largura em G, o caminho mínimo de origem única é calculado em tempo θ(V² ).
• B. aplicando a busca em largura no grafo transposto G^T = (V, E^T ), o caminho mínimo de origem única é calculado em tempo θ(V² ).
• C. 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).
• D. aplicando a busca em profundidade no grafo transposto G^T = (V, E^T ), o caminho mínimo de origem única é calculado em tempo θ(V + E).
• E. relaxando as arestas pela busca em profundidade no grafo de entrada G = (V, E) e, posteriormente, aplicando a busca em profundidade no grafo transposto G^T = (V, E^T ), o caminho mínimo de origem única é calculado em tempo θ(V² ).

Gabarito: C

Comentários

• GABARITO LETRA C

  Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida.

  FONTE: https://pt.wikipedia.org/wiki/Problema_do_caminho_m%C3%ADnimo