jor

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre o algoritmo de Dijkstra, quais das alternativas abaixo está correta?

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

Idéia original de: Jorge Augusto Hongo