MO417 - Questão para a prova oral

Número: 2010-088

Enunciado: Considere os algoritmos de Bellman-Ford, Caminhos Mínimos para Grafos Acíclicos Direcionados (utilizando ordenação topológica) e o de Dijkstra. Considere também dois tipos de grafos direcionados, conforme listados abaixo:

• G₁: acíclico, contendo somente arestas negativas.
• G₂: contém apenas arestas positivas e pelo menos um ciclo.

Desejamos agora passar G₁ e G₂ como entrada para cada um dos algoritmos citados acima, com o intuito de resolver o problema de encontrar todos os caminhos mínimos entre um dado vértice de origem e todos os outros vértices. Quantos desses algoritmos irão resolver corretamente esse problema, para cada um dos respectivos grafos?

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

Ideia original de: Marcos Vinícius Mussel Cirne