MO417 - Questão para a prova oral

Número: 123

Enunciado:
Com relação à algoritmos de caminhos mais curtos de única origem e as afirmações abaixo sobre o algoritmo de Bellman-Ford, assinale a alternativa correta:

Seja s o vértice de origem e w o peso das arestas:

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 theta(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

Autor(a): Nelson Luiz Geromel Ra: 958097