Question

Leia o excerto a seguir.

“[...] um exemplo clássico do uso de algoritmos é a tabela que se consulta atlas e guias rodoviários, que dão as distâncias de várias cidades. Atualmente, fazemos esse tipo de consulta, porém com a utilização de programas computacionais que efetuam os cálculos.”


CORMEN, J. Desmistificando Algoritmos. Rio de Janeiro: Elsevier, 2017. p. 93.

Considerando o exposto, sobre o algoritmo de Floyd-Warshall, analise as afirmativas a seguir.

I. O algoritmo de Floyd utiliza a recursividade para determinar o menor custo, porém não poderia ser utilizado para a consulta de guias rodoviários.
II. O algoritmo de Floyd resolve os problemas menores e, gradativamente, vai resolvendo problemas mais complexos.
III. O algoritmo de Floyd utiliza valores negativos nas arestas entre os vértices.
IV. O algoritmo de Floyd busca fazer a eliminação de vértices para se obter uma estrutura mínima.

Está correto o que se afirma em:


III, apenas.
II e III, apenas.
II, apenas.
II, III e IV, apenas.
I, II e IV, apenas.

Answer 1

Resposta:

II, apenas

Explicação:

A afirmativa I está incorreta, pois o algoritmo de Floyd não utiliza a recursividade. Na afirmativa III, declara-se que são tratados os valores negativos, porém o algoritmo de Floyd não faz o cálculo com custos negativos. Por esse motivo, ela está incorreta, pois, no algoritmo de Floyd, não seria possível encontrar custos negativos. A afirmativa IV está incorreta, uma vez que o algoritmo de Floyd não tem como objetivo eliminar vértices ou arestas, mas, sim, encontrar o caminho de menor custo entre os vértices.