MO417 - Questão para a prova oral
Número: 148
Enunciado:
Sobre o algoritmo de Floyd-Warshall é INCORRETO afirmar:
- O algortimo utiliza o paradigma de programação dinâmica.
- O algoritmo executa em tempo Θ(n3),
onde n é a ordem da matriz de entrada W (com
os pesos das arestas) do algoritmo, ou seja, W é nxn.
- É 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 dij < n; do contrário, teremos dij = ∞
- 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 dii é negativo para algum vértice i, então esse vértice pertence a pelo menos um ciclo de peso negativo.
- NDA
Informação útil:
dij é o peso de um caminho mais curto do vértice i para o vértice j, e D = (dij), conforme notação utilizada no livro texto da disciplina.
Autor(a): Jonathas Campi Costa