arm

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Qual das seguintes declarações não é correta?

1. FASTER-ALL-PAIRS-SHORTEST-PATH tem complexidade em tempo de O(n³lg n) e Θ(n²) do espaço, se um grafo com n vertices esta representado através de uma matriz de adjacência.
2. Se há um ciclo negativo no grafo G, depois de aplicar o algoritmo Floyd-Warshall(G), existe alguns u∈V de tal modo que δ(u,u)<0, (seja δ(i,j) a tabela dos caminhos mais curtos entre o vertice i e o vertice j).
3. Uma implementaçao ineficiente do algoritmo Dijkstra não afeta negativamente a complexidade do algoritmo Johnson.
4. Se um grafo G contem arestas com pesos negativos, o algoritmo Johnson muda os valores dos pesos nas arestas, de tal modo que nenhuma aresta tem peso negativo, usando uma função que preserva os ciclos negativos em G (se existirem).
5. NDA.

Ideia original de: Armando Faz Hernández