MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-082

Enunciado: A matriz de peso abaixo, representa o grafo G=( V, E) acíclico orientado ponderado. Em cada célula dessa matriz, representada pela linha u e coluna v, é armazenado o peso w da aresta (u,v). Um peso infinito (∞) significa que (u,v) ∉ E.

\	R	S	T	U	V
R	∞	1	2	∞	-1
S	∞	∞	∞	-3	-1
T	∞	-2	∞	-1	∞
U	∞	∞	∞	∞	1
V	∞	∞	∞	∞	∞

Denotamos por δ(u, v) o caminho mais curto a partir do vértice u até o vértice v no grafo. Assinale a alternativa correta:

1. δ( R, S) = 1
2. δ( R, U) = 1
3. δ( R, V) = -2
4. δ( T, V) = 0
5. NDA

Ideia original de: Ademar Takeo Akabane