Assunto: Caminhos mais curtos de todos os pares e Fluxo máximo
Enunciado
Escolha a alternativa correta:
A) Para obter os caminhos mínimos de todos os pares basta executar |V|-1 vezes o MATRIX-MULTIPLY(A,B) sobre a matriz de pesos W, operação que resulta em W|V|-1. Isto se deve à similaridade do algoritmo de caminhos mais curtos com a multiplicação de matrizes.
B) O valor do fluxo máximo de uma rede de fluxos é definido pelo corte que tem a maior capacitade entre todos os possíveis.
C) O tempo de execução do algoritmo de Floyd-Warshall pode ser melhorado para Θ(V2) se este for adaptado para usar uma matriz no lugar de |V|.
D) Numa rede residual as arestas podem assumir valores positivos apenas.
E) N.D.A.