Questão para a Prova Oral 158

Semana: 19/05/2003 a 23/05/2003

Assunto: Caminhos mais curtos de única origem

Enunciado
Em relação aos algoritmos para o problema de caminhos mais curtos de única origem em grafos, é CORRETO afirmar:

A) O algoritmo de Bellman-Ford pode ser aplicado em grafos no qual todos os pesos de arestas são não negativos.
B) O tempo de execução do algoritmo de Bellman-Ford é O(V * E).
C) O algoritmo de Dijkstra pode ser aplicado em grafos no qual os pesos das arestas podem ser negativos.
D) O tempo de execução do algoritmo de Dijkstra é Theta(V + E).
E) N.D.A.

Marcelo Fantinato
RA: 000472