MO417 - Questão para a prova oral

Número: 140

Enunciado:
É sabido que o algoritmo de Dijkstra, apresentado abaixo, pode ser implementado utilizando diferentes implementações da fila de prioridades Q presente no algoritmo. Para implementações utilizando heaps binários, heaps binomiais e, heaps de Fibonacci, respectivamente, podemos afirmar que os tempos totais de execução são:

DIJKSTRA(G, w, s)  
     INITIALIZE-SINGLE-SOURCE(G, s)
     S ← vazio
     Q ← V[G]
     while Q ≠ vazio
           do u ← EXTRACT-MIN(Q)
               S ← S ∪ {u}
               for cada vertice v pertencente a Adj[u]
                     do RELAX(u,v,w)


INITIALIZE-SINGLE-SOURCE(G, s) 
     for cada vertice v pertencente a V|G| do 
             do d[v]  ←   ∞
                predecessor[v] ← NIL
     d[s] ← 0 

RELAX(u, v, w)
     if d[v] > d[u] + w(u,v)
        then d[v] ← d[u] + w(u, v)
             predecessor[v] ← u 

1. O(E + lg(V)), O(V lg(V)), O((V+E)lg(V))
2. O(E lg(V)), O(V lg(V)), O(V lg(V) + V)
3. O(E lg(V)), O(V lg(V) + E), O(V lg(V))
4. O(E lg(V)), O((V+E)lg(V)), O(V lg(V) + E)
5. NDA

Autor(a): Jonathas Campi Costa