MO417 - Questão para a prova oral

Número: 2010-081

Enunciado: No algoritmo de Bellman-Ford, uma rodada de relaxações em todas as arestas é executada exatamente V-1 vezes, onde V é o número de arestas no grafo. Considere um algoritmo que execute apenas n rodadas de relaxação, para n < V-1. O que pode-se dizer sobre ele?

1. Que qualquer distância envolvendo um número de arestas menor ou igual a n será corretamente calculada.
2. Que qualquer caminho mínimo de peso menor ou igual a n será encontrado.
3. Que qualquer caminho mínimo envolvendo um número de arestas menor ou igual a n será encontrado.
4. Que, se na última rodada (a de número n) ainda ocorreram atualizações, então há um ciclo negativo que envolve até n arestas.
5. NDA

Ideia original de: Alexandre Tachard Passos