MO417 - Questão para a prova oral

Número: 148

Enunciado:
Sobre o algoritmo de Floyd-Warshall é INCORRETO afirmar:

1. O algortimo utiliza o paradigma de programação dinâmica.
2. O algoritmo executa em tempo Θ(n³), onde n é a ordem da matriz de entrada W (com os pesos das arestas) do algoritmo, ou seja, W é n_xn.
3. É possível computar o fecho transitivo de um grafo orientado com o auxílio do algoritmo de Floyd-Warshall, bastando associar a cada aresta do grafo um peso de valor 1 e executar o algoritmo de Floyd-Warshall. Se houver um caminho do vértice i para o vértice j, então d_ij < n; do contrário, teremos d_ij = ∞
4. Pode-se utilizar o algoritmo de Floyd-Warshall para detectar a presença de ciclos de peso negativo em um grafo orientado. Para isso, basta executar o algoritmo de Floyd-Warshall e analisar a matriz D de pesos de caminhos mais curtos, para a presença de valores negativos na diagonal principal. Se d_ii é negativo para algum vértice i, então esse vértice pertence a pelo menos um ciclo de peso negativo.
5. NDA

Informação útil:

d_ij é o peso de um caminho mais curto do vértice i para o vértice j, e D = (d_ij), conforme notação utilizada no livro texto da disciplina.

Autor(a): Jonathas Campi Costa