daf

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Assinale a alternativa que melhor relaciona os itens abaixo aos algoritmos:

1. Devolve resposta para grafos nos quais os pesos das arestas podem ser negativos.
2. É um algoritmo que exibe semelhança tanto em relação à busca em largura quanto em relação ao algoritmo de Prim para calcular árvores espalhadas mínimas.
3. Utiliza técnica de reponderação das arestas.
4. É executado no tempo θ (V³)
5. Na execução desse algoritmo, uma aresta pode ser relaxada mais de uma vez.

a) As alternativas 1 e 2 estão relacionadas ao algoritmo de Dijkstra.
b) As alternativas 1 e 5 estão relacionadas ao algoritmo de Bellman-Ford.
c) As alternativas 1, 2, 3 e 4 estão relacionadas ao algoritmo de Johnson.
d) As alternativas 1, 2, 3 e 4 estão relacionadas ao algoritmo de Floyd-Warshall.
e) N.D.A

Ideia original de: Danielle Furtado dos Santos Dias