car

MO417 - Questão para a prova oral

Número:

Enunciado: Dado o seguinte grafo dirigido G=(V, E), com pesos nas arestas:

Y o resultado de calcular todos os caminhos com Slow-All-Pairs-Shortest-Paths:

cuales som os valores da tabela que faltam?

a) U = 7, V = 2, W = 1, X =  -4, Y = 3, Z = 6
b) U = -7, V = -4, W = -4, X =  -1, Y = -6, Z = 4
c) U = 7, V = 5, W = -3, X =  -2, Y = 6, Z = -4
d) U = 7, V = 4, W = 4, X =  1, Y = 6, Z = -4
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales

fab

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Qual a diferença entre o custo total da árvore espalhada mínima e o custo total da árvore com caminhos mínimos a partir do vértice A até todos os outros vértices do grafo abaixo?

A) 0
B) 1
C) 2
D) 3
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

arm

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Qual das seguintes declarações não é correta?

1. FASTER-ALL-PAIRS-SHORTEST-PATH tem complexidade em tempo de O(n³lg n) e Θ(n²) do espaço, se um grafo com n vertices esta representado através de uma matriz de adjacência.
2. Se há um ciclo negativo no grafo G, depois de aplicar o algoritmo Floyd-Warshall(G), existe alguns u∈V de tal modo que δ(u,u)<0, (seja δ(i,j) a tabela dos caminhos mais curtos entre o vertice i e o vertice j).
3. Uma implementaçao ineficiente do algoritmo Dijkstra não afeta negativamente a complexidade do algoritmo Johnson.
4. Se um grafo G contem arestas com pesos negativos, o algoritmo Johnson muda os valores dos pesos nas arestas, de tal modo que nenhuma aresta tem peso negativo, usando uma função que preserva os ciclos negativos em G (se existirem).
5. NDA.

Ideia original de: Armando Faz Hernández

ali

MO417 - Questão para a prova oral

Número:

Enunciado: Com relação aos passos descritos pelos algoritmos de Bellman-Ford, DAG e Dijkstra(Usando uma heap de fibonacci.), julgue as alternativas que completam corretamente a tabela abaixo:

I. A=SIM e C=NÃO.
II.  D=O(V.E) e E=O(V+E).
III.  B=SIM.

a) Todas as afirmações são verdadeiras.
b) Somente as afirmações I e II são verdadeiras.
c) Somente as afirmações II e III são verdadeiras.
d) Somente as afirmações I e III são verdadeiras.
e) NDA.

Ideia original de: Alisson Linhares de Carvalho

acs

MO417- QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado o grafo abaixo:

É correto afirmar:

1. O algoritmo de Dijkstra retorna os caminhos máximos.
2. Bellman-Ford é o melhor algoritmo para encontrar os caminhos mínimos neste grafo.
3. Se Bellman-Ford for executado utilizando a mesma ordem de visitação de Dijkstra, eles terão o mesmo tempo de execução.
4. Pode-se encontrar os caminhos mínimos a partir de qualquer origem em tempo O(V + E)
5. NDA 

Ideia original de: Anderson Carlos Sousa e Santos

eri

MO417 - Questão para a prova oral

Número:

Enunciado : De acordo com o grafo abaixo, marque a alternativa correta considerando a aplicação do algoritmo DAG-SHORTEST_PATHS.

DAG-SHORTEST-PATHS(G,w, s)
1 topologically sort the vertices of G
2 INITIALIZE-SINGLE-SOURCE(G, s)
3 for each vertex u, taken in topologically sorted order
4      do for each vertex v ∈ Adj[u]
5           do RELAX(u, v,w)

 

a)      O “menor custo” entre o vértice A e o vértice E é 7.

b)     O “menor custo” entre o vértice B e o vértice E é 6.

c)      O “menor custo” entre o vértice A e o vértice F é 7.

d)     O “menor custo” entre o vértice B e o vértice F é 4.

e)      N.D.A. 

Ideia original de:  Erick Aguiar Donato

dam

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Em um famoso título de video game, o herói deve percorrer um reinado para salvar sua princesa, presa em um castelo. Para expressar o progresso do personagem durante a aventura, é disponibilizado um mapa semelhante ao da figura abaixo, mas com uma extensão maior. Nele, cada ponto destacado (com uma "moeda") é uma fase, e o herói avança pelos caminhos a partir do ponto inicial (START), podendo escolher uma próxima fase sempre que vencer a atual.

Sabendo que todas as fases têm a mesma dificuldade e duram praticamente o mesmo tempo, um garoto deseja terminar o jogo da forma mais rápida possível, para que ainda lhe sobre tempo para estudar.

Nesta situação, NÃO É ÚTIL para planejar a mínima sequência de fases que se precisa jogar, do ponto inicial (START) até o castelo:
I) Aplicar busca em largura a partir do ponto inicial.
II) Aplicar busca em profundidade a partir do ponto inicial.
III) Aplicar o algoritmo de Prim a partir do ponto inicial.
IV) Aplicar o algoritmo de Dijkstra a partir do ponto inicial.

Escolha a alternativa verdadeira:

1. Todas as afirmativas estão incorretas.
2. Apenas as afirmativas I, III e IV estão incorretas.
3. Apenas as afirmativas I, II e IV estão incorretas.
4. Apenas as afirmativas I e IV estão incorretas.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira

eds

MO417 - Questão para a prova oral
Número:

Enunciado: Imagine que tomemos  as operações normais de soma e multiplicação definidas na matemática para operação de matrizes provindas de grafos. Imagine também que grafos tenham apenas peso iguais a 1.
Então afirma-se que:

1  A potenciação da matriz pelo expoente x, pode nos mostrar os caminhos de tamanho x.
2  Se for feita a potenciação de matriz pelo expoente x, os valores 0 nos mostrarão que não existe caminho de tamanho n entre dois vértices.
3 Existe a possibilidade de se calcular os menores caminhos utilizando as operações normais de matrizes.

a. Todas  as afirmações estão corretas
b. Somente a afirmação 1 é correta.
c. Somente a afirmação 2 é correta.
d. Somente as afirmações 1 e 2 são corretas.
e. NDA

Ideia original de: Edson Riberto Bollis

ant

MO417 - Questão para a prova oral

Número: 

Enunciado: Dado o seguinte grafo dirigido G=(V,E):
 

  

Seja w e W a função de peso e a matriz de pesos do grafo G respetivamente. Suponha que seu vetor de listas de adjacência como seus lista de adjacência de cada vértice estam armazenados em orden alfabética. Assinale alternativa correta sobre os caminhos mais curtos entre todos os pares de vértices do grafo G: 

1.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em Θ( 5³), também o caminho mais longo dos caminhos mais cortos é  d_ea= 16. 

2.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em Θ( 5² lg 5 + 45), também o caminho mais longo dos caminhos mais cortos é  d_ed= 15.

3.)Johnson(G,w) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em O( 5³), também o caminho mais longo dos caminhos mais cortos é  d_ea= 16.
4.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em O( 5² lg 5 + 45), também o caminho mais longo dos caminhos mais cortos é  d_ed= 15.
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga

dac

MO417 - Questao para a prova oral 

Numero:

Enunciado:  Em relação ao algoritmo Floyd-Warshall avalie as asserções abaixo.

I   É permitida arestas de peso negativo.

II   Seu custo de armazenamento é Ω(n²).

III  É executável em Θ(V³).

a. Apenas a alternativa II está correta.

b. Apenas as alternativas I e II estão corretas.

c. Todas as alternativas estão corretas.

d. Apenas a alternativa I está incorreta.

e. NDA

Ideia original de: Danilo Carneiro

jac

MO417 - Questão para a prova oral

Número:

Enunciado: Dadas as matrizes predecessoras gerada pela execução do algoritmo Floyd-Warshall sobre um grafo orientado, indique qual o caminho mais curto com origem no vértice 3 e destino no vértice 1.

a) 3->2->1
b) 3->2->4->1
c) 3->4->2->1
d)3->1
e) NDA 

Ideia original de: Jacqueline Midlej do Espírito Santo

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

ade

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: A matriz de peso abaixo, representa o grafo G=( V, E) acíclico orientado ponderado. Em cada célula dessa matriz, representada pela linha u e coluna v, é armazenado o peso w da aresta (u,v).

\	R	S	T	U	V
R	∞	1	2	∞	-1
S	∞	∞	∞	-3	-1
T	∞	-2	∞	-1	∞
U	∞	∞	∞	∞	1
V	∞	∞	∞	∞	∞

OBS: w = ∞, significa que  (u,v) ∉ E.

Denotamos por δ(u, v) o caminho mais curto a partir do vértice u até o vértice v no grafo.
Assinale a alternativa correta:

a) δ( R, V) = -2
b) δ( R, S) = 1
c) δ( T, V) = 0
d) δ( R, U) = 1
e) NDA


Ideia original de: Ademar Takeo Akabane

wel

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: O mapa abaixo apresenta uma parte do Backbone de Internet no Brasil e ao lado é apresentada a lista de adjacências entre os roteadores, com os seus respectivos custos de envio em um determinado momento.
Assumindo que roteamento dos dados é feito apenas através do protocolo OSPF (Open Shortest Path First), que é uma implementação do algoritmo de Dijkstra, qual seria o caminho percorrido pelos dados enviados do Rio Grande do Sul (RS) para a Bahia (BA)?


a. RS, PR, SP, MG, BA
b. RS, PR, SP, RJ, ES, BA
c. RS, SC, SP, MG, DF, RJ, ES, BA
d. RS, SC, SP, RJ, DF, MG, BA
e. NDA

Ideia original de: Anderson Coelho Weller

dav

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Sobre o tempo de execução de cálculo de caminho mínimo entre dois vértices em um grafo de V vértices e E arestas é INCORRETO afirmar:

1. O tempo de execução pode ser  o(V*E) somente se não houver ciclos ou se não houver arestas com pesos negativos
2. Se não houver ciclos no grafo, o tempo de execução pode pertencer a O(V+E)
3. O tempo de execução é O(V*E) para qualquer grafo que contenha ciclos e arestas de pesos negativos
4. Para qualquer grafo que contém ciclos e não contém arestas de peso negativo o tempo de execução pode  pertencer a O(V^2)
5. NDA

Ideia original de: Daniel Vidal

hil

Número:

Enunciado: Um professor de Complexidade de Algoritmos pediu para os alunos construírem caminhos mínimos a partir de um vértice de origem s até todos os outros vértices do grafo, mas adicionou a seguinte restrição: "Caso haja mais de um caminho mínimo (com mesmo peso total) do vértice de origem até um certo vértice v, deve-se optar pelo caminho mínimo contendo o menor número de arestas". Um dos alunos optou por simplesmente executar o algoritmo de Dijkstra, sem nenhuma adaptação, mantendo inclusive a função de relaxamento original, mostrada a seguir:

RELAX (u, v, w)
   if v.d > u.d + w(u,v)
      v.d = u.d + w(u,v)
      v.π = u

Para quais valores de a, b, c, d e e no grafo abaixo o aluno encontraria o resultado esperado pelo professor (partindo do vértice 1)?

1. a = 4, b = 7, c = 2, d = 1, e = 2.
2. a = 7, b = 4, c = 1, d = 1, e = 3.
3. a = 4, b = 7, c = 4, d = 3, e = 2.
4. a = 7, b = 5, c = 2, d = 1, e = 1.
5. N. D. A.

Ideia original de: Hilário Seibel Júnior

2013-05-24

jun2

MO417 - Questão para a prova oral

Numero:

Enunciado: Leia a seguintes afirmações e assinale a alternativa Correta

I          O algoritmo de Dijkstra é um algoritmo guloso (greedy algorithm), O algoritmo de Floyd-Warshall é um algoritmo de programação dinâmica (dinamic-programming algorithm).

II        Se o grafo G= (V, E) não contem nenhum ciclo de peso negativo accessível a partir da origem s, então para todo v ∈ V, o peso do caminho mais curto &(s, v) permanece bem definido, mesmo tendo um valor negativo.

III       Se o grafo G= (V, E) contem um ciclo de peso negativo accessível a partir da origem s, então para todo v ∈ V, os pesos dos caminhos mais curto &(s, v) não são bem definido.

IV       Seja o grafo G= (V, E). Se existe um ciclo de peso negativo em algum caminho desde s ate v, definimos &(s,v) = 0 , E se não existe caminho desde um s ate t, temos que &(s, t) =. ∞

V        Caminhos mais curtos (shortest paths) não são necessariamente únicos, mas os arvores de caminhos mais curtos (shortest-paths trees) se são únicos.
 
Qual é a alternativa correta:

a) Somente I , II , III e IV são corretas

b) Somente I , II e III são corretas

c) Somente I , II , III , IV e V são corretas

d) Somente I , IV são corretas

e) NDA

                                             Ideia original de: Junior Cupe Casquina

mig2

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado:  Você está jogando um jogo online chamado DotA. Percebendo que você pode converter o mapa do jogo em um grafo com vértices representando as posições no mapa e as arestas os caminhos até eles, você observa que cada passagem no grafo provoca uma quantidade diferente de danos à você no jogo. É possível ainda alterar o grafo para usar pesos para representar os danos causados ​​por cada aresta. Você então, usa o algoritmo de Dijkstra para encontrar o caminho de A a H, com o menor dano possível. Anote a ordem em que os vértices são removidos da fila de prioridade ao executar o algoritmo de Dijkstra.

(a) A, B, D, C, F, E, G, H 

(b) A, B, C, D, F, E, G, H

(c) A, B, D, C, E, F, G, H

(d) A, B, C, D, E, F, G, H

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

kim

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre os algoritmos de grafos, assinale a alternativa que contém os itens corretos:

I - O algoritmo de Prim tem desempenho equivalente ao algoritmo de Kruskal quando o grafo é esparso.

II - O Algoritmo de Bellman-Ford tem desempenho superior ao algoritmo de Dijkstra em grafos orientados com pesos negativos.

III - A ordenação topológica de um grafo utiliza a busca em profundidade para encontrar o tempo de término de cada vértice, e dessa forma organizar os vértices de forma que eles fiquem ordenados decrescentemente pelo tempo de término. O algoritmo só funciona em grafos acíclicos não-orientados.

IV - Durante a execução do algoritmo de busca em profundidade, encontrar uma aresta de retorno indica que o grafo não é acíclico.

V - A melhor estrutura de dados para o algoritmo de Prim são as Heaps de Fibonacci, fazendo a complexidade do algoritmo ser O(E + V lg V).

(a) I, II e IV.

(b) II, III e V.

(c) I, IV e V.
(d) II, IV e V. 

(e) N.D.A 

Idéia original de: Kim Pontes Braga

mps

MO417 - Questão para a prova oral

Número

Enunciado: Dado um Grafo G = (G, A), quando se aplica os algoritmos de Kruskal e Prim, qual é o percorrido que fazem os algoritmos para encontrar a árvore espalhada mínima.

a) Kruskal (A->D, C->E, D->F, A->B, B->E, E->G) - Prim (A->D, D->F, A->B, B->E, E->C, E->G)
b) Kruskal (A->B, C->D, D->F, B->E, A->B, E->G) - Prim (A->D, A->F, A->B, B->E, E->G, B->C)
c) Kruskal (A->B, C->E, D->F, A->B, B->E, E->G) - Prim (A->D, C->E, D->F, B->E, A->B, E->G)
d) Kruskal (A->D, F->G, D->F, B->E, C->B, E->G) - Prim (A->D, A->F, C->B, B->E, F->G, B->D)
e) DNA

Idea Ogirinal: Marcelo Palma Salas

vla

MO417 - QUESTÃO PARA A PROVA ORAL
Número:
Dados o grafo G e os algoritmos para encontrar os caminhos mais curtos em um grafo.

Verificar as afirmações:

I. Sé as linhas 5-8 do algoritmo de Bellman-Ford são adicionadas no final do algoritmo de Dijkstra, este poderia encontrar o caminho mais curto em um grafo com arestas negativas.
II. O algoritmo DAG-SHORTEST-PHATS encontra o caminho mais longo sé cada peso do grafo é transformado por F(w)=-1*w
III. Um ciclo negativo é caracterizado porque a suma de suas arestas é um valor negativo.
IV. O grafo G da figura é resolvido pelo algoritmo de Bellman-Ford pois -5+2>0

São corretas:
a. somente II e III
b. somente I e II
c. somente II, III e IV
d. somente I, II e III
e. DNA

Ideia original de: Vladimir Jaime Rocca Layza

ren

MO417 - Questão para a prova oral

Número:

Enunciado: É dado o seguinte grafo direcionado com pesos descrito por uma matriz de adjacências,  em que uma entrada (i,j) diferente de 0 na matriz significa que há uma aresta de i para j.

Lembre-se

   a  b  c  d

a| 0 -5 -3  0

b| 5  3  1  2

c| 4 -1  0  1

d| 0  0  2  0

Quais são, respectivamente, as distâncias mínimas entre o vértice inicial a e o final d, e entre o inicial d e o final a?

a)  -5 e -3
b)  -3 e 6
c)  -4 e -3
d)  -1 e -6
e)  N.D.A.

Ideia original de:  René du Raymond Sacramento

tha

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o grafo direcional ponderado G abaixo, onde a fonte é o vértice t.

Considere as seguintes afirmações abaixo e assinale a alternativa correta:

I) Ao aplicarmos o algoritmo de Bellman-Ford em G, relaxando as arestas na ordem (u,v), (u,x), (u,z), (v,u), (v,z), (v,x), (x,z), (t,u), (t,x), o algoritmo com o código abaixo retorna TRUE.
BELLMAN-FORD(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
para i=1 ate |V[G]| -1
   para cada aresta (u,v) pertencente a E[G]
       RELAX(u,v,w)
   para cada aresta (u,v) pertencente a E[G]
      se (v.d > u.d + w(u,v))
           return FALSE
return TRUE

II) Se eliminássemos a aresta de peso negativo (v,u) do grafo G, poderíamos aplicar o algoritmo de Dijkstra no grafo alterado, G', cujo código segue abaixo.
DIJKSTRA(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
S = vazio
Q = V[G]
while Q != vazio
    u = EXTRACT-MIN(Q)
    S = S U {u}
    para cada vértice v pertencente a G.Adj[u]
         RELAX(u,v,w)
Dado que o laço while itera |V| vezes, após a quarta iteração do laço teríamos a seguinte situação (obs: vertice.d representa o peso de um caminho mínimo da fonte até o vértice v):
S = {t,u,x,v}; t.pai = NILL; t.d = 0; u.pai = t; u.d = 7; v.pai = u; v.d = 15; x.pai = u; x.d = 9; z.pai = u; z.d = 18.

III) Se retirássemos a aresta (v,u) do grafo G, obtendo o grafo G', seria possível fazer uma ordenação topológica dos vértices do grafo G' e encontrar caminhos mínimos de fonte única, obtendo a situação final (obs: vertice.d representa o peso de um caminho mínimo da fonte até o vértice v):
t.pai = NILL; t.d = 0; u.pai = t; u.d = 7; v.pai = u; v.d = 15; x.pai = u; x.d = 9; z.pai = v; z.d = 17.

A) Apenas III é correta
B) Apenas II é correta
C) II e III são corretas
D) I e II são corretas
E) N.D.A


Ideia original de: Thaís Harumi Ussami

luc

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

fel

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Seja G o grafo com 5 nós e 7 arestas abaixo.

Qual os valores dos pesos de aresta a, b e c (podendo ser negativos) que causariam o algoritmo de Dijkstra retornar um caminho mínimo correto para G tendo o nó 1 como origem?

A) a = 5, b = -6, c = 10;
B) a = 12, b = -4, c = 1;
C) a = 14, b = -6, c = 8;
D) a = 8, b = -5, c = 5;
E) NDA

Ideia original de: Félix Carvalho Rodrigues

she

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: 

Tem-se que conectar um conjunto de computadores entre eles com cabo de rede, só se pode conectar um computador diretamente com outro sem usar nenhum outro dispositivo, no seguinte grafo estão representados os computadores como vértices e as distancias mínimas em metros que um cabo pode recorrer entre cada dois computadores, como arestas. Indique qual seria o custo mínimo en reais para conecta-los, tomando em conta que cada metro de cabo custa 1.5 reais.

a) 84.0
b) 55.0
c) 82.5
d) 61.5
e) NDA

Ideia original de: Sheila Katherine Venero Ferro

ota

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.

mar

MO417 - Questão para a prova oral

Número:

Enunciado: No seguinte grafo não orientado ponderado aplique o algoritmo de Kruskal e responda corretamente:

Qual dos seguintes conjuntos de arestas não são parte de nenhuma das possíveis árvores espalhadas mínimas:

a) {(a,b), (b,d), (d,e)}
b) {(a,d), (c,b), (c,f)}

c) {(b,c), (d,e), (f,g)}

d) {(b,c), (b,d), (f,g)}

e) NDA

Idéia original de: Marleny Luque Carbajal

rap

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado o grafo abaixo, qual das alternativas apresenta o vértice com distância e pai corretos para o menor caminho que se percorre a partir do vértice a?

a) b: d = 3, p = a
b) c: d = 7, p = f
c) d: d = 8, p = c
d) e: d = 10, p = d
e) NDA

Ideia original de: Raphael Azzolini

pau

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-

Enunciado: Dado o grafo ponderado e orientado G = (V, E) abaixo, considere as seguintes afirmações:

1. Se aplicarmos o algoritmo de BELLMAN-FORD, tendo o vértice u como fonte, o algoritmo retornará verdadeiro.
2. Se aplicarmos o algoritmo de DIJKSTRA, ainda que haja uma aresta com peso negativo, por não haverem ciclos negativos, o algoritmo calculará corretamente os caminhos mais curtos, tomando qualquer vértice como fonte.
3. Se retirarmos a aresta (t, v) poderemos aplicar o algortimo DAG-SHORTEST-PATHS, tomando qualquer como fonte.

É correto concluir que:

a) Apenas a 1 é verdadeira.

b) 1 e 2 são falsas.

c) 2 e 3 são verdadeiras.

d) Apenas a 2 é falsa.

e) N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus