ota

MO417- Questão para a prova oral
Numero:


Existem diversas abordagens para resolver o problema do menor caminho entre todos os pares de vértices em um grafo. Analise o grafo direcionado ponderado abaixo e as afirmações sobre ele.

I. É possível executar o algoritmo de  Dijkstra para cada um dos vértices como fonte, assim obtendo o menor caminho entre cada par de vértices.
II. Como não se trata de um grafo esparso, o custo de execução do algoritmo de Bellman Ford, para cada um dos vértices como fonte, será inferior ao custo do Floyd-Warshall.
III. Caso o peso da aresta entre os vértices 5 e 2 fosse -2,  apenas o algoritmo Floyd-Warshall resolveria o problema do enunciado, pois é o único que faz uso de Programação Dinâmica.
IV.  Suponha a seguinte alteração nos laços aninhados do algoritmo Floyd-Warshall:

for k from 1 to |V|
      for i from 1 to |V|
         for j from 1 to |V|
            if d[i][k] + d[k][j] < d[i][j] then
               d[i][j] ← d[i][k] + d[k][j]
               salvo[i][j] ← k

       Seria possível, em O(V), imprimir o menor caminho entre quaisquer pares de vértices, pois basta varrer o caminho {i,...j} em "salvo" .


Sobre aquelas afirmativas , é(são) correta(s) apenas:
a. I e II
b. I e III
c. II e IV
d. I e IV
e. N.D.A

Ideia original de: Otavio Augusto A Silva.