Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Programa de Pós-Graduação em Ciência da Computação
Grafos
4ª Lista de Exercícios
1) É possível usar simplesmente o algoritmo de busca em largura para encontrar o
caminho mínimo entre dois vértices de um grafo valorado em termos dos pesos
de cada aresta? Por quê?
2) Avalie a veracidade da seguinte afirmativa:
“Algoritmos de caminhos mínimos usam a técnica de relaxamento, que decresce
um limite superior (upper bound) para a distância mínima para cada vértice. Isso
é feito até que o limite superior se torne menor ou igual a própria distância.”
3) O que calcula o algoritmo de Dijkstra? Apesar de ser um algoritmo guloso, por
que Dijkstra funciona?
4) É possível que exista um outro caminho de igual peso entre dois vértices de um
grafo valorado além daquele encontrado pelo algoritmo de Dijkstra? Por quê?
5) Para o grafo G (V, E) apresentado abaixo encontre os menores caminhos entre o
vértice 0 (zero) e os demais vértices de G. Use o algoritmo de Dijkstra.
6) Implemente em uma linguagem de programação a sua escolha o algoritmo de
Dijkstra. Em seguida, trabalhe os itens abaixo:
a. Use o grafo G, apresentado na Questão 5, como entrada do algoritmo
implementado e confirme o resultado antes encontrado. Apresente o log
de execução.
b. O desempenho do algoritmo de Dijkstra depende da estrutura de dados
usada para controlar sua fila de prioridade. Dito isso, faça uma análise de
desempenho no tempo do algoritmo implementado comparando as
estruturas de vetor, heap binário e heap de Fibonacci ao controlar sua
fila de prioridade. Apresente gráficos. Uma sugestão é expandir o grafo
G em número de vértices e arcos.
7) Implemente em uma linguagem de programação a sua escolha o algoritmo de
Bellman-Ford. Em seguida, trabalhe os itens abaixo:
a. Use o grafo G’ = (V, E) orientado e ponderado abaixo como entrada do
algoritmo implementado e encontre os menores caminhos entre o vértice
S e os demais vértices de G’. Apresente o log de execução.
b. Qual é a complexidade no tempo do algoritmo implementado? Caso mais
arcos fossem inseridos no grafo G’, como a complexidade no tempo
seria afetada? Usando dados reais, ilustre graficamente sua explicação.
c. Usando o algoritmo de Dijkstra, implementado na Questão 6, encontre os
menores caminhos entre o vértice S (fonte) e os demais vértices de G’.
Especifique a estrutura de dados utilizada para implementar sua fila de
prioridade. O tempo de execução foi menor ou maior que o obtido com o
algoritmo de Bellman-Ford? Por quê?
d. Modifique o valor (peso) da aresta (X, U) para -3. Em seguida, repita os
itens (a) e (c). Explique a influência dessa modificação na execução dos
algoritmos implementados.
8) Implemente em uma linguagem de programação a sua escolha o algoritmo de
Floyd-Warshall. O algoritmo deve identificar a presença de ciclos negativos. Em
seguida, trabalhe os itens abaixo:
a. Use o grafo G’, apresentado na Questão 7, como entrada do algoritmo
implementado e encontre o caminho mais curto para todos os pares de
vértices de G’. Apresente o log de execução.
b. Use as implementações de Bellman-Ford e Dijkstra para encontrar o
caminho mais curto para todos os pares de vértices de G’. Especifique a
estrutura de dados utilizada para implementar a fila de prioridade no
algoritmo de Dijkstra. O tempo de execução foi menor ou maior que o
obtido com o algoritmo de Floyd-Warshall? Por quê?
c. Modifique o valor (peso) da aresta (X, U) no grafo G’ para -3. Em
seguida, repita o item (a). Explique a influência dessa modificação na
execução do algoritmo implementado.