MO417 - Questão para a prova oral

Número: 093

Enunciado:
Considere o grafo orientado ponderado e o algoritmo de relaxação a seguir. Qual das afirmações a seguir é falsa, dado que o algoritmo de Dijkstra foi usado para calcular os caminhos mínimos com origem em A?

RELAX(u, v, w)
1 if d[v] > d[u] + w(u, v)
2    then d[v] ← d[u] + w(u, v)
3         pai[v] ← u
      

1. O caminho mínimo de A até I passa por B
2. O caminho mínimo de A até G passa por F
3. O predecessor de E é C
4. G não é predecessor de nenhum vértice
5. NDA

Autor(a): Greice Martins de Freitas