MO417 - Questão para a Prova Oral

Número: 2003-156

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), bastando 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 indica corretamente a impossibilidade de determinar caminhos mínimos para o grafo.
E) N.D.A.


Ideia original de: Bruno Cedraz Brandão