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.

MO417 - Questão para a prova oral
Numero:
 

O algoritmo de Dijkstra resolve o problema do caminho mais curto em um grafo, dada uma fonte desse caminho, com tempo de execução em O(E+VlogV), caso seja usada um Heap de Fibonacci como a fila de prio deste algoritmo.

Entretanto diversas aplicações estão interessadas em um caminho mais curto entre A e B, ou de uma fonte A ao destino B. Sobre a alteração deste algoritmo para dijkstra_ab(G,A,B) , é correto afirmar:

I.   Como o algoritmo funciona apenas em grafos direcionados, não existe a garantia de sempre encontrar B partindo de A. 
II.  Caso haja uma aresta de peso negativo entre A e B, o menor caminho pode estar contido em um ciclo.
III. Não é possível escrever dijkstra_ab(G,A,B) fazendo-se apenas uma alteração em dijkstra(G,A).
IV.  Apesar de na média dijkstra_ab(G,A,B) ter um tempo de execução inferior, este ainda é O(E+VlogV).
 
a. I e III estão corretas.
b. I e IV estão corretas.
c. III está correta.
d. II e IV estão corretas.
e. N.D.A

Ideia original de: Otavio Augusto A Silva.
 

MO417 - Questão para a prova oral
Numero:

Seja H=(V,E) um grafo não direcionado, representado por uma Matriz de Adjacência, onde existe apenas um caminho entre cada par (u,v) ∈ V,  e as propriedades de um  heap-máximo sejam verdadeiras.
Sobre o custo de implementarmos as funções pai(u) e  raiz(H), é correto afirmar:

a.  Se apenas acessássemos v ∈ V na diagonal superior de H,  poderíamos em o(V) obter pai(u) e  raiz(H).
b. Caso H seja transformado em uma Lista de Adjacência , ambas as funções terão custo O(V).
c. Se H fosse um grafo direcionado, o custo de pai(u) seria O(E).
d. Sendo O(depth) o custo de uma busca em profundidade em H, e O(root) o custo de raiz(H), para qualquer tamanho de V,  root=Ω(depth) .
e. N.D.A 

Ideia original de: Otávio Augusto Araújo Silva