MO417 - Questão para a prova oral

Número: 141

Enunciado:
Sobre caminhos mais curtos de única origem em um gao, dado o algoritmo:

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)

e o grafo acima, determine o "custo" do caminho mais curto entre os vértices s e o vértices z aplicando o algoritmo.

1. 7
2. 3
3. 4
4. ∞
5. NDA

Autor: Washington Luís Pereira Barbosa (971766)