Enunciado:
Para um grafo acíclico orientado(DAG) ponderado, pode-se afirmar:

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

Autor(a): Fabio Batista Gomes
RA: 022256