MO417 - Questão para a prova oral

Número: 2013-074

Enunciado: Sobre o algoritmo de caminhos mínimos de Dijkstra, qual das alternativas abaixo está correta?

a. O algoritmo pode ser considerado como um algoritmo guloso
b. Dijkstra encontra os caminhos mais curtos mesmo com arestas de peso negativo, desde que não haja ciclos negativos
c. O algoritmo funciona apenas se não houver ciclos, ou seja, se o grafo de entrada for um DAG (Directed Acyclic Graph)
d. O algoritmo relaxa cada aresta duas vezes
e. NDA

Ideia original de: Jorge Augusto Hongo