tia

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado o grafo dirigido G = (V, E), a função de pesos das areas w e os algoritmos abaixo:

Assinale a alternativa que contém o valor d correto de cada um dos vértices do grafo G, após a execução do algoritmo DIJKSTRA-MODIFIED(G, w, z).

DIJKSTRA-MODIFIED(G, w, s)
  INITIALIZE-SINGLE-SOURCE-MODIFIED(G, s)
  Q = G.V
  while Q != ∅
    u = EXTRACT-MAX(Q)
    for each vertex v ∈ G.adj[u]
      RELAX-MODIFIED(u, v, w)

INITIALIZE-SINGLE-SOURCE-MODIFIED(G, s)
  for each vertex v ∈ G.V
    v.d = -∞
  s.d = 0

RELAX-MODIFIED(u, v, w)
  if v.d < u.d + w(u, v)
    v.d = u.d + w(u, v)

A) s.d = 3, t.d = 6, y.d = 8, x.d = 7, z.d = 0

B) s.d = 3, t.d = 6, y.d = 8, x.d = 12, z.d = 0

C) s.d = 3, t.d = 9, y.d = 11, x.d = 15, z.d = 14

D) s.d = 3, t.d = 9, y.d = 11, x.d = 12, z.d = 17

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade