Questão para a Prova Oral 156

Assunto: Caminhos mais curtos de única orígem

Enunciado
Sobre algoritmos para caminhos mais curtos de origem única é certo afirmar:

A) Dijkstra, quando implementado com heap de Fibonacci, pode ser usado no lugar de Bellman-Ford em todos os casos.
B) A partir do topological-sort é possível encontrar os caminhos mais curtos em Θ(E+V), basta o grafo não possuir ciclos negativos.
C) No algoritmo de Dijkstra a ordem de pesquisa dos vértices é idêntica à de uma busca em largura.
D) Na presença de ciclos negativos, o algoritmo de Bellman-Ford notifica corretamente a impossíbilidade de determinar os caminhos mínimos para o grafo.
E) N.D.A.

Autor: Bruno Cedraz Brandão
RA: 022245