MO417 - Questão para a prova oral
Número: 146
Enunciado:
O problema de encontrar caminhos mais curtos de todos os pares
consiste em encontrar um caminho de peso mínimo para todos os pares de
vértices de um grafo que represente tal problema. Alguns algoritmos resolvem
este problema aplicando diferentes técnicas. É importante saber as suas
características principais para definir quando utilizar um ou outro. Dado as
afirmações sobre os algoritmos de caminhos mais curtos de todos os pares
abaixo, assinale a alternativa verdadeira:
I. O algoritmo de Floyd-Warshall é um algoritmo de programação dinâmica que
consegue resolver problemas com arestas de peso negativo e é executado no tempo
de O(V3), onde V é o número de vértices do grafo que representa o problema.
II.O algoritmo de Johnson utiliza a técnica de reponderação para transformar
arestas com pesos negativos em arestas com peso não negativo.
III. Para
calcular caminhos mais curtos de todos os pares, o algoritmo de Johnson
emprega o algoritmo de Bellman-Ford e não o algoritmo de Dijkstra, já que
este último não pode ser aplicado em problemas com arestas com peso negativo.
IV.
É possível utilizar uma abordagem de semelhante à multiplicação de matrizes
- problema que pode ser resolvido com programação dinâmica - para resolver o
problema de caminhos mais curtos de todos os pares. A técnica elevação ao
quadrado repetida utiliza essa abordagem e suporta arestas com pesos
negativos.
-
As afirmações I, II e IV estão corretas.
-
As afirmações I e IV estão incorretas.
-
Somente a afirmação IV está incorreta.
-
Somente as afirmações II e IV estão corretas.
- NDA
Autor(a): Paulo Gurgel Pinheiro