MO417 - Questão para a prova oral

Número: 2009-134

Enunciado: Considerando o grafo apresentado abaixo e o algoritmo de Dijkstra, que resolve o problema de caminhos mais curtos de única origem, assinale a alternativa que contém a ordem CORRETA em que os vértices são retirados da fila de prioridade mínima usada pelo algoritmo, e o maior caminho entre os caminhos mais curtos.  Considere que a origem é o vértice s.

1. s, a, b, c, d. Maior caminho com tamanho 21.
2. s, a, c, b, d. Maior caminho com tamanho 19.
3. s, a, c, d, b. Maior caminho com tamanho 19.
4. s, a, d, c, b. Maior caminho com tamanho 21.
5. NDA

Ideia original de: Gabriel de Souza Fedel