kim

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre os algoritmos de Floyd-Warshall e Johnson, assinale a alternativa que contém as afirmativas verdadeiras:

I - O algoritmo de Floyd-Warshall tem complexidade O(n³).

II - O Algoritmo de Johnson usa os algoritmos de Dijkstra e Bellman-Ford como sub-rotinas baseado na existência de arestas de peso negativo.

III - Se o Algoritmo de Johnson usar o algoritmo de Dijkstra sua complexidade é O(V² lg V + VE).

IV - O algoritmo de Floyd-Warshall tem desempenho superior ao de Johnson em grafos esparsos.

V - O algoritmo de Johnson usa lista de adjacências ao invés de matriz de adjacências.

(a) I, II e IV.

(b) I, II e V.
(c) II, III e V.

(d) II, IV e V.

(e) N.D.A

Idéia original de: Kim Pontes Braga