MO417 - Questão para a prova oral

Número: 2009-123

Enunciado: Considere um grafo G com pesos nas arestas dados pelo vetor w, e origem s.  Com relação ao algoritmo de Bellman-Ford codificado abaixo, a às afirmações a seguir, assinale a alternativa correta:

BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
for i ← to |V[G]| - 1 do
     for cada aresta (u, v) pertencente a E|G| do
          RELAX(u, v ,w)
for cada aresta (u, v) pertencente a E|G| do
     if d[v] > d[u] + w(u, v) then
          Return FALSE
return TRUE

INITIALIZE-SINGLE-SOURCE(G, s)
for cada vertice v pertencente a V|G| do
     d[v] ← infinito
     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 algoritmo resolve o problema de caminhos mais curtos de única origem, mesmo com arestas de peso negativo.
2 - O algoritmo detecta a existência de ciclos de peso negativo acessíveis a partir da origem.
3 - O algoritmo é executado em tempo Θ(V + E) se não houver ciclos e arestas de peso negativo.
4 - Cada aresta é relaxada apenas uma vez.

Alternativas

1. Somente as afirmações 1 e 3 estão certas.
2. Somente as afirmações 2 e 4 estão certas.
3. Somente as afirmações 3 e 4 estão certas.
4. Somente as afirmações 1 e 2 estão certas.
5. NDA

Ideia original de: Nelson Luiz Geromel