MO417 - Questão para a prova oral

Número: 2010-076

Enunciado: No grafo orientado ponderado G a seguir, o valor dentro de cada vértice x indica o peso de um caminho mais curto da origem s até x. Assinale a alternativa CORRETA:


I. Existem oito árvores distintas de caminhos mínimos com 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 de ciclos no grafo G.

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

Ideia original de: Priscila Tiemi Maeda Saito