caminhos mínimos

Prévia do material em texto

5. Caminhos Mı´nimos
1. Decida se as afirmac¸o˜es abaixo sa˜o verdadeiras ou falsas, justificando apropriadamente:
(a) A a´rvore determinada pela aplicac¸a˜o do algoritmo de Dijkstra (formada pelas arestas de pi)
tambe´m e´ uma a´rvore geradora mı´nima.
(b) Seja T uma a´rvore geradora mı´nima de um grafo G, e considere dois ve´rtices u e v em G.
Enta˜o, para determinar um caminho de peso mı´nimo em G entre u e v, basta considerar o peso
do caminho entre u e v em T .
(c) Se P e´ um caminho de peso mı´nimo entre os ve´rtices u e v em um grafo direcionado com
pesos na˜o negativos nas arestas G, enta˜o P continua sendo um caminho de peso mı´nimo entre
os ve´rtices u e v no grafo G quando as arestas tem seus pesos alterados de p(e) para p(e) + 10.
(d) Se P e´ um caminho de peso mı´nimo entre os ve´rtices u e v em um grafo direcionado com
pesos na˜o negativos nas arestas G, enta˜o P continua sendo um caminho de peso mı´nimo entre
os ve´rtices u e v no grafo G quando as arestas tem seus pesos alterados de p(e) para 10p(e).
2. O que acontece se o algoritmo de Dijkstra for aplicado a um digrafo que conte´m um ciclo em que
todas as arestas teˆm pesos negativos? Isto e´, mostre exatamente qual e´ o ponto do algoritmo
que pode dar errado, neste caso, baseado em um grafo fixo, usado como exemplo.
3. Modifique o algoritmo de Dijkstra de modo a poder determinar os caminhos mı´nimos a partir
de u e na˜o so´ os valores das distaˆncias.
Deˆ o algoritmo que, dados u e v dois ve´rtices do grafo, da´ um caminho (isto e´, a sequeˆncia de
ve´rtices) de peso mı´nimo entre u e v e seu peso.
4. Escreva na notac¸a˜o usada nesta disciplina, um algoritmo que tem como entrada um grafo di-
recionado ac´ıclico com pesos na˜o negativos nas arestas e um ve´rtice s, inicializa a distaˆncia da
fonte s para cada ve´rtice v de V (G) \ {s} como d(v) = +∞, d(s) = 0. Considera os ve´rtices em
uma ordenac¸a˜o topolo´gica e, a partir de s segue a ordem da ot, atualizando d(w) para todo w
na lista de adjaceˆncias de sa´ıda do ve´rtice corrente.
Prove que este algoritmo de fato determina o peso do menor caminho de s a cada ve´rtice de G
e analise a sua complexidade.
5. (Ex. 25.2-4 CLRS) Mostre que a retirada dos superescritos ((k) e (k − 1)) do algoritmo de
Floyd-Warshall esta´ correto, produzindo um algoritmo que tem complexidade de espac¸o Θ(n2).
6. (Ex. 25.2-6 CLRS) Como que a sa´ıda do Algoritmo de Floyd-Warshall pode ser usada para
detectar a existeˆncia de um ciclo de peso negativo no grafo?
7. Se os pesos das arestas do grafo G dado forem nu´meros naturais, considere a seguinte ideia para
encontrar um caminho mı´nimo entre um par de ve´rtices ainda usando busca em largura: crie
um grafo H com os mesmos ve´rtices de G e, ao inves de uma aresta uv de peso p, construa em
H um caminho entre u e v com p− 1 ve´rtices intermedia´rios (novos). Na˜o ha´ pesos nas arestas
de H. Execute em H uma busca em largura com raiz igual a um dos ve´rtices a que se quer
encontrar a distaˆncia. Esta ideia esta correta? Qual e´ a sua complexidade?