MO417 - Questão para a prova oral

Número: 075

Enunciado:
Dados o algoritmo de caminho mais curto de única origem de Bellman-Ford, o grafo orientado G, a ordem de passagem pelas arestas para relaxamento sendo (s,t), (s,y), (t,x), (y,z), (t,y), (y,x), (z,x), (x,t) e o grafo modificado G':

Para se chegar a configuração de relaxamento apresentada em G' são necessárias quantas passagens pelas arestas na ordem especificada:

1. 1
2. 2
3. 3
4. 4
5. NDA

Autor: Juliana Galvani Greghi