MO417 - Questão para a prova oral

Número: 135

Enunciado:
Sobre os algoritmos de caminhos mais curtos de única origem, assinale a alternativa INCORRETA:

1. O algoritmo de Dijkstra é um algoritmo guloso.
2. O algoritmo de Dijkstra funciona tanto para grafos orientados quanto para grafos não orientados, desde que os pesos de todas as arestas sejam positivos.
3. O algoritmo de Dijkstra sempre apresenta o mesmo tempo de execução, independentemente de como a fila de prioridade mínima é implementada.
4. Em grafos orientados acíclicos existe algoritmo de complexidade O(|V|+|E|) para determinar os caminhos mínimos a partir de única origem. Basta calcular os caminhos mínimos analisando os vértices segundo a ordenação topológica.
5. NDA

Autor(a): Ana Carolina Correia Rézio.