mps

MO417 - Questão para a prova oral

Número:

Seja g um grafo dirigido e ponderado. Para calcular o menor dos caminhos minimos entres dois vértices quaisquer do grafo, podemos aplicar o algoritmo de Floyd. Dada a matriz L de adjacência do grafo g, que calcula uma matriz D com a distância de caminho mínimo que liga dois vértices. 

Algoritmo_de_Floyd(L, D, n)
1. let L[1..n][1..n] and D[1..n][1..n] be new arrays
2. for i=1 to n
3.     for j=1 to n
4.         D[i,j] = L[i,j]
5. for k=1 to n
6.     for i=1 to n
7.         for j=1 to n
8.             D[i,j]=Min2(D[i,j],D[i,k]+D[k,j])

Onde n é o número de vértices do grafo

Qual das seguintes afirmações é correta respeito da Programação Dinámica.

a) Este algoritmo pode ser resolvido com a Programação Dinâmica, com a recorrência: Dk(i,j)=Min{D_k-1(i,k), D_k-1(k,j)}
b) Este algoritmo pode ser resolvido com a Programação Dinâmica porque não são encontrados subproblemas sobrepostos.
c) Este algoritmo não pode ser resolvido com a Programação Dinâmica porque os subproblemas são independentes.
d) Este algoritmo não necessita ser resolvido com a Programação Dinâmica, porque o algoritmo tem um tempo linear.
e) NDA

Ideia original de: Marcelo Palma Salas RA 089053