Número: 2013-
Enunciado: Dado o grafo ponderado e
orientado G = (V, E) abaixo, considere as seguintes afirmações:
- Se aplicarmos o algoritmo de BELLMAN-FORD, tendo o vértice u como fonte, o algoritmo retornará verdadeiro.
- Se aplicarmos o algoritmo de DIJKSTRA, ainda que haja uma aresta com peso negativo, por não haverem ciclos negativos, o algoritmo calculará corretamente os caminhos mais curtos, tomando qualquer vértice como fonte.
- Se retirarmos a aresta (t, v) poderemos aplicar o algortimo DAG-SHORTEST-PATHS, tomando qualquer como fonte.
É correto concluir que:
a)
Apenas a 1 é verdadeira.
b) 1 e 2 são falsas.
c) 2 e 3 são verdadeiras.
d)
Apenas a 2 é falsa.
e)
N.D.A.
Ideia
original de: Paulo Henrique Hack de Jesus
Nenhum comentário:
Postar um comentário