eri

MO417 - Questão para a prova oral

Número:

Enunciado : De acordo com o grafo abaixo, marque a alternativa correta considerando a aplicação do algoritmo DAG-SHORTEST_PATHS.

DAG-SHORTEST-PATHS(G,w, s)
1 topologically sort the vertices of G
2 INITIALIZE-SINGLE-SOURCE(G, s)
3 for each vertex u, taken in topologically sorted order
4      do for each vertex v ∈ Adj[u]
5           do RELAX(u, v,w)

 

a)      O “menor custo” entre o vértice A e o vértice E é 7.

b)     O “menor custo” entre o vértice B e o vértice E é 6.

c)      O “menor custo” entre o vértice A e o vértice F é 7.

d)     O “menor custo” entre o vértice B e o vértice F é 4.

e)      N.D.A. 

Ideia original de:  Erick Aguiar Donato