sábado, 18 de maio de 2013

vla

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