MO417 - QUESTÃO PARA A PROVA ORAL
Número:
Dados o grafo G e os algoritmos para encontrar os caminhos mais curtos em um grafo.
Verificar as afirmações:
I. Sé as linhas 5-8 do algoritmo de Bellman-Ford são adicionadas no
final do algoritmo de Dijkstra, este poderia encontrar o caminho mais
curto em um grafo com arestas negativas.
II. O algoritmo DAG-SHORTEST-PHATS encontra o caminho mais longo sé cada peso do grafo é transformado por F(w)=-1*w
III. Um ciclo negativo é caracterizado porque a suma de suas arestas é um valor negativo.
IV. O grafo G da figura é resolvido pelo algoritmo de Bellman-Ford pois -5+2>0
São corretas:
a. somente II e III
b. somente I e II
c. somente II, III e IV
d. somente I, II e III
e. DNA
Ideia original de: Vladimir Jaime Rocca Layza
Nenhum comentário:
Postar um comentário