MO417 - Questão para a prova oral

Número: 124

Enunciado:
Dadas afirmações a seguir sobre caminhos mais curtos de única origem em um grafo, assinale a alternativa correta:

I - Esse problema possui como subestrutura ótima o fato de que um caminho mais curto entre dois vértices contém outros caminhos mais curtos em seu interior.

II - Um caminho mais curto entre dois vértices pode não ser o único.

III - Caminhos mais curtos não podem conter ciclos de peso negativo.

1. Todas as afirmações estão corretas.
2. Apenas as afirmações I e II estão corretas.
3. Apenas as afirmações I e III estão corretas.
4. Apenas as afirmações II e III estão corretas.
5. NDA

Autor(a): Renato Hirata