MO417 - Questão para a prova oral

Número: 092

Enunciado:
Para esta questão, considere que w(v,u) corresponde ao peso de uma aresta que liga o vértice v ao vértice u.
Considere também a seguinte implementação do algoritmo de DIJKSTRA

DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 S ← ∅
3 Q ← V[G]
4 while Q ≠ ∅ do
5   u ← EXTRACT-MIN(Q)
6   S ← S ∪ {u}
7   for each vertex v ∈ Adj[u]  do
8     RELAX(u,v,w)
      

1. As operações (implícitas e explícitas) sobre a fila de prioridades, Q, requeridas pelo algoritmo de Dijkstra são INSERT, DECREASE-KEY e EXTRACT-MIN.
2. O algoritmo de Dijkstra só funciona quando para cada tripla de arestas (u,v), (u,a) e (a,v) temos w(u,v) >= w(u,a) + w(a,v)
3. Se todas as arestas de um grafo possuirem pesos distintos, então o caminho mais curto entre dois vértices é único.
4. Seja λ() uma função que associa um valor aos vértices de um grafo G. Se G for alterado de forma que os pesos w(u,v) das arestas sejam transformados em w'(u,v)= w(u,v) - λ(u) + λ(v), então os caminhos mínimos no grafo modificado e no grafo original são os mesmos.
5. NDA

Autor(a): Leonardo de Paula Rosa Piga