gui

MO417 - Questão para a prova oral

Número:

Enunciado: Sabemos que o algoritmo Bellman-Ford resolve o problema de caminhos mais curtos de única ordem no caso mais geral, no qual os pesos das arestas podem ser negativos. Considere o grafo abaixo e, começando pelo vértice z, assinale qual alternativa correta.

a) z.d = 0      w.d = 7   u.d = 13   x.d = 20
    z.π = NIL  w. π = z  u. π = w   x. π = w

b) z.d = 0      x.d = 6   u.d = 2    y.d = 10
    z.π = NIL  x. π = z  u. π = x   y. π = u

c) z.d = 0      w.d = 7   y.d = 16  x.d = 12  u.d = 8
    z.π = NIL  w. π = z  y. π = w  x. π = y   u. π = x

d) z.d = 0      w.d = 7   u.d = 13   y.d = 21  x.d = 17
    z.π = NIL  w. π = z  u. π = w   y. π = u   x. π = y

e) NDA
 

Ideia original de: Luís Guilherme Cordiolli Russi