MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considerando os algoritmos de Bellman-Ford, Dag-Shortest-Paths ou Dijkstra, analise os grafos abaixo e indique quais destes algoritmos podem ser utilizados para encontrar um caminho mais curto a partir do vértice s.

 Grafo 1:

Grafo 2:

Grafo 3:

a) Grafo 1: Dijkstra e Dag-Shortest-Paths. Grafo 2: Bellman-Ford e Dijkstra. Grafo 3: Dag-Shortest-Paths e Bellman-Ford

b) Grafo 1: Bellman-Ford. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford e Dijkstra

c) Grafo 1: Nenhum dos algoritmos. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford e Dijkstra

d) Grafo 1: Bellman-Ford. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford, Dag-Shortest-Paths e Dijkstra

e) NDA

Ideia original de: Lucas Oliveira Batista