MO417 - Questão para a prova oral

Número: 2013-080

Enunciado: Um professor de Complexidade de Algoritmos pediu para os alunos construírem caminhos mínimos a partir de um vértice de origem s até todos os outros vértices do grafo, mas adicionou a seguinte restrição: "Caso haja mais de um caminho mínimo (com mesmo peso total) do vértice de origem até um certo vértice v, deve-se optar por um caminho mínimo contendo o menor número de arestas". Um dos alunos decidiu simplesmente executar o algoritmo de Dijkstra, sem nenhuma adaptação, mantendo inclusive a função de relaxamento original, mostrada a seguir:

RELAX (u, v, w)
   if v.d > u.d + w(u,v)
      v.d = u.d + w(u,v)
      v.π = u

Para quais valores de a, b, c, d e e no grafo abaixo o aluno encontraria o resultado esperado pelo professor (partindo do vértice 1)?

1. a = 4, b = 7, c = 2, d = 1, e = 2.
2. a = 4, b = 7, c = 4, d = 3, e = 2.
3. a = 7, b = 4, c = 1, d = 1, e = 3.
4. a = 7, b = 5, c = 2, d = 1, e = 1.
5. N. D. A.

Ideia original de: Hilário Seibel Júnior