Caminhos mínimos

Questões-guia:

1. O que é o problema de passeios mínimos de fonte fixa num grafo orientado ponderado?
2. Vamos estudar também o problema com fonte e destino fixos?  Por quê?
3. O que é sub-estrutura ótima?  O problema de passeios mínimos tem esta propriedade?  De que forma?
4. 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?
5. Qual é a saída típica de um algoritmo para resolver o problema de caminhos mínimos?
6. Segundo Cormen, o que são a inicialização e o relaxamento?  Por que o relaxamento tem este nome?
7. 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?
8. 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?
9. 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?
10. 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.

1. 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.
2. Implemente DAG-SHORTEST-PATHS em LEMON, seguindo um bom esquema JSP.  Teste com o exemplo da Figura 24.5.
3. LEMON já tem uma implementação de Dijsktra.  Teste com o exemplo da Figura 24.6.