Questão para a Prova Oral 166

Semana: 02/06/2003 a 06/06/2003

Assunto: Caminhos mais curtos de todos os pares e Fluxo máximo (Parte 1)

Enunciado
Em relação ao problema de “Caminhos Mais Curtos de Todos os Pares”, é INCORRETO afirmar:

A) Embora seja possível resolver um problema de caminhos mais curtos de todos os pares executando um algoritmo de caminhos mais curtos de única origem |V| vezes, o desempenho dessa solução não é é o melhor possível.
B) A maioria dos algoritmos para resolver este problema utiliza uma representação de matriz de adjacências.
C) O algoritmo de Floyd-Warshall é executado no tempo Theta(V³ lg V).
D) O algoritmo de Floyd-Warshall é um algoritmo que utiliza a abordagem de programação dinâmica.
E) N.D.A.

Marcelo Fantinato
RA: 000472