Questão para a prova oral 168 (Semana 13: Caminhos mais curtos de todos os pares e Fluxo máximo I)
Enunciado:
Com relação aos algoritmos vistos em aula de caminhos mais curtos de todos os pares, assinale a alternativa INCORRETA:
A) É possível, porém ineficiente, usar o algoritmo de Bellman-Ford, |V| vezes, uma para cada vértice usado como a origem, para resolver o problema de caminhos mais curtos de todos os pares.
B) Os tempos de execução dos algoritmos SLOW-ALL-PAIRS-SHORTEST-PATHS e FASTER-ALL-PAIRS-SHORTEST-PATHS, são respectivamente, Theta(V4) e Theta(V3 lg V).
C) No algoritmo de Floyd-Warshall, a caracterização da estrutura de um caminho mais curto é idêntica à que é usada nos algoritmos de todos os pares baseados na multiplicação de matrizes.
D) O objetivo do fecho transitivo de um grafo orientado é descobrir se existe um caminho em G = (V,E) desde i até j para todos os pares de vértices i,j pertencentes a V.
E) NDA.