Questões-guia:
- O que é o problema de passeios mínimos de fonte fixa num grafo orientado ponderado?
- Vamos estudar também o problema com fonte e destino fixos? Por quê?
- O que é sub-estrutura ótima? O problema de passeios mínimos tem esta propriedade? De que forma?
- O que ocorre se o grafo tiver ciclos negativos? E se tiver arestas negativas, mas não ciclos negativos? Qual a relação entre passeios mínimos e caminhos mínimos?
- Qual é a saída típica de um algoritmo para resolver o problema de caminhos mínimos?
- Segundo Cormen, o que são a inicialização e o relaxamento? Por que o relaxamento tem este nome?
- Quais as 6 propriedades fundamentais de algoritmos que usam a inicialização de Cormen e modificam as estimativas de caminhos mínimos apenas através de passos de relaxamento?
- Faça um diagrama JSP do algoritmo de Bellman-Ford. Tente usar não mais que 10 caixas. Permite arestas negativas? Ciclos negativos? Há restrições à estrutura do grafo? Qual sua complexidade?
- Faça um diagrama JSP do algoritmo para caminhos mínimos num DAG. Tente usar não mais
que 7 caixas. Permite arestas negativas? Ciclos negativos? Há restrições à estrutura do grafo? Qual sua complexidade?
- Faça um diagrama JSP do algoritmo de Dijkstra. Tente usar não mais
que 8 caixas. Permite arestas negativas? Ciclos negativos? Há restrições à estrutura do grafo? Qual sua complexidade?
Exercícios:
ATENÇÃO: ao testar os programas nos grafos, não construa os grafos no código. Faça um arquivo LGF para o grafo e leia este arquivo no código.
- Implemente Bellman-Ford em LEMON, seguindo um bom esquema JSP. Teste com o exemplo da Figura 24.4. A seguir, modifique o exemplo para conter um ciclo negativo, e teste novamente.
- Implemente DAG-SHORTEST-PATHS em LEMON, seguindo um bom esquema JSP. Teste com o exemplo da Figura 24.5.
- LEMON já tem uma implementação de Dijsktra. Teste com o exemplo da Figura 24.6.
Nenhum comentário:
Postar um comentário