MO417 - Questão para a prova oral

Número: 076

Enunciado:
Dado o grafo orientado ponderado G=(V, E) e o problema de caminhos mais curtos de uma única origem, assinale a alternativa CORRETA:

Considere que o valor, apresentado dentro de cada vértice, representa o peso de seu caminho mais curto a partir da origem s.

I. Dependendo da ordem em que são relaxadas as arestas, podemos formar oito árvores distintas de caminhos mais curtos com a mesma raiz s.

II. Os valores de d[s], d[a], d[b], d[c] e d[d] são 0, -4, 4, -1 e 7, respectivamente.

III. Os valores de d[e], d[f] e d[g] são todos iguais a infinito.

IV. Não existem caminhos mais curtos, devido à existência de arestas de peso negativo e ciclos no grafo G(V, E).

1. Todas as alternativas são corretas
2. Apenas II e III são corretas
3. Apenas III e IV são incorretas
4. Apenas IV é incorreta
5. NDA

Autor(a): Priscila Tiemi Maeda Saito