ota

MO417 - Questão para a prova oral
Numero:
 

O algoritmo de Dijkstra resolve o problema do caminho mais curto em um grafo, dada uma fonte desse caminho, com tempo de execução em O(E+VlogV), caso seja usada um Heap de Fibonacci como a fila de prio deste algoritmo.

Entretanto diversas aplicações estão interessadas em um caminho mais curto entre A e B, ou de uma fonte A ao destino B. Sobre a alteração deste algoritmo para dijkstra_ab(G,A,B) , é correto afirmar:

I.   Como o algoritmo funciona apenas em grafos direcionados, não existe a garantia de sempre encontrar B partindo de A. 
II.  Caso haja uma aresta de peso negativo entre A e B, o menor caminho pode estar contido em um ciclo.
III. Não é possível escrever dijkstra_ab(G,A,B) fazendo-se apenas uma alteração em dijkstra(G,A).
IV.  Apesar de na média dijkstra_ab(G,A,B) ter um tempo de execução inferior, este ainda é O(E+VlogV).
 
a. I e III estão corretas.
b. I e IV estão corretas.
c. III está correta.
d. II e IV estão corretas.
e. N.D.A

Ideia original de: Otavio Augusto A Silva.