MO417 - Questão para a prova oral

Número: 2010-093

Enunciado: Considere o grafo orientado ponderado a seguir. Qual das alternativas é falsa, dado que o algoritmo de Dijkstra foi usado para calcular os caminhos mínimos com origem em A, usando o algoritmo de relaxação abaixo, onde "d" é a estimativa de distância mantida pelo algoritmo, "w" dá os pesos das arestas, e "pai" indica o predecessor de cada vértice?

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

Ideia original de: Greice Martins de Freitas