MO417 - Questão para a prova oral

Número: 091

Enunciado:
Considere as seguintes afirmações sobre o algoritmo de Dijkstra:

I - Seu tempo de execução assintótico será superior ao do algoritmo de Bellman-Ford caso a fila de prioridades utilizada pelo algoritmo seja implementada utilizando-se um heap de Fibonacci.
II - Se a fila de prioridades utilizada pelo algoritmo for implementada utilizando-se um heap binomial, sua complexidade temporal seria O((E+V)lg(V)).
III - Tanto o algoritmo de Dijkstra quanto o de algoritmo de Bellman-Ford não tem restrições quanto a grafos com arestas de peso negativo, porém apenas Bellman-Ford é capaz de identificar ciclos negativos.
IV - Se a fila de prioridades utilizada pelo algoritmo for implementada utilizando-se um heap de Fibonacci, sua complexidade temporal seria O(E + V lg(V)).

Assinale a alternativa correta:
  1. Apenas II e IV estão corretas
  2. Apenas I e II estão incorretas
  3. Apenas I e IV estão corretas
  4. Apenas I está incorreta
  5. NDA

Autor(a): Matheus Silva Mota