jun2

MO417 - Questão para a prova oral

Numero:

Enunciado: Leia a seguintes afirmações e assinale a alternativa Correta

I          O algoritmo de Dijkstra é um algoritmo guloso (greedy algorithm), O algoritmo de Floyd-Warshall é um algoritmo de programação dinâmica (dinamic-programming algorithm).

II        Se o grafo G= (V, E) não contem nenhum ciclo de peso negativo accessível a partir da origem s, então para todo v ∈ V, o peso do caminho mais curto &(s, v) permanece bem definido, mesmo tendo um valor negativo.

III       Se o grafo G= (V, E) contem um ciclo de peso negativo accessível a partir da origem s, então para todo v ∈ V, os pesos dos caminhos mais curto &(s, v) não são bem definido.

IV       Seja o grafo G= (V, E). Se existe um ciclo de peso negativo em algum caminho desde s ate v, definimos &(s,v) = 0 , E se não existe caminho desde um s ate t, temos que &(s, t) =. ∞

V        Caminhos mais curtos (shortest paths) não são necessariamente únicos, mas os arvores de caminhos mais curtos (shortest-paths trees) se são únicos.
 
Qual é a alternativa correta:

a) Somente I , II , III e IV são corretas

b) Somente I , II e III são corretas

c) Somente I , II , III , IV e V são corretas

d) Somente I , IV são corretas

e) NDA

                                             Ideia original de: Junior Cupe Casquina