MO417 - Questão para a prova oral

Número: 143

Enunciado:
Sobre os algoritmos para caminhos mais curtos BELLMAN-FORD, DAG-SHORTEST-PATHS e DIJKSTRA, qual das proposições está correta:

1. Qualquer grafo acíclico direcionado pode ser resolvido pelo algoritmo Dijkstra, mesmo se possuir arestas com pesos negativos, desde que não tenha ciclos negativos.
2. Dependendo da escolha do vértice de origem, s, ao fim da execução do algoritmo DAG-SHORTEST-PATHS, quando todas as arestas já foram relaxadas e, consequentemente, os caminhos mais curtos para todos os destinos já estão bem definidos, podem existir vértices com valores infinitos.
3. Como o algoritmo DAG-SHORTEST-PATHS requer ordenação topológica, ele apresenta tempo de execução pior do que os algoritmos Bellman-Ford e Dijkstra.
4. Ambos algoritmos de BELLMAN-FORD e DIJKSTRA apresentam mesma complexidade assintótica, cuja ordem de crescimento é cúbica.
5. NDA

Autor(a): Gabriela Batista Leão.