MO417 - Questão para a prova oral
Número: 077
Enunciado:
Sobre caminhos mínimos e o algoritmo de Bellman-Ford assinale a
alternativa incorreta.
- Se um grafo dirigido com pesos nas arestas possui um
caminho a→b→c que é minimo, então o
subcaminho b→c também é mínimo.
- Não existem caminhos mínimos a partir de uma fonte única em um
grafo dirigido com pesos nas arestas que possui algum ciclo
negativo.
- Uma operação de relaxação reduz ou mantém igual o limitante
superior para o peso de um caminho mínimo que vai da
origem s a um dado vértice v.
- O algoritmo de Bellman-Ford busca caminhos mínimos a partir de
um vértice s aplicando O(E*V) operações de relaxação nas
arestas.
- NDA
Autor(a): Leonardo de Paula Rosa Piga