MO417 - Questão para a prova oral
Número: 2003-160Enunciado: Para um grafo acíclico orientado (DAG) ponderado, com V vértices e E arestas, pode-se afirmar que:
A) A melhor solução para se encontrar caminhos mais curtos de única origem é através do algoritmo de Dijkstra.
B) É possível encontrar todos os caminhos mais curtos de única origem em tempo O(V lgV).
C) O fato de ser acíclico e orientado possibilita a utilização de ordenação topológica de seus vértices para encontrar todos caminhos mais curtos a partir de uma origem, o que reduz o tempo de execução para O(V + E).
D) Utilizando-se ordenação topológica, deve-se fazer V passagens sobre todos os vértices na seqüência topológica ordenada. À cada passagem por um vértice, deve-se relaxar todas suas arestas.
E) NDA
Ideia original de: Fabio Batista Gomes
Nenhum comentário:
Postar um comentário