MO417 - Questão para a prova oral
Número: 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:
- G1: acíclico, contendo somente arestas negativas.
- G2: contém apenas arestas positivas e pelo menos um ciclo.
Desejamos agora passar G1 e G2 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.
- 2, 1.
- 2, 2.
- NDA
Autor(a): Marcos Vinícius Mussel Cirne