MO417 - Questão para a prova oral
Número: 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?
- Que qualquer distância envolvendo um número de arestas
menor ou igual a n será corretamente calculada.
- Que qualquer caminho mínimo de peso menor ou igual a n será
encontrado.
- Que qualquer caminho mínimo envolvendo um número de arestas
menor ou igual a n será encontrado.
- 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.
- NDA
Autor(a): Alexandre Tachard Passos