Caminhos em Grafos

• Caminhos simples

Caminhos mais curtos

• Aplicações; grafos não ponderados e grafos ponderados
• Caminhos de fonte única, de fonte e destino e com multiplicidade de fontes e destinos
• Conceito de relaxação de aresta e de nós e testes associados

Algoritmo de Dijkstra

• Discussão; Semelhançãs com PRIM e DFS/BFS: procura generalizada
• Implementação tipo; Exemplo de aplicação
• Propriedades do algoritmo de Dijkstra
• Análise de complexidade

SPT's de todos para todos

• Por aplicação repetida do algoritmo de Dijkstra
• Algoritmo de Floyd
  • Breve referência e exemplo de execução

Árvores mínimas de suporte - MST

• Propostas de solução para cálculo de MST
  • Algoritmo de Prim
    • Descrição; Implementação; Exemplo de execução; Análise de eficiência
  • Algoritmo de Kruskal
    • Descrição; Implementação; Exemplo de execução; Análise de eficiência
  • Algoritmo de Boruvka
    • Breve referência ao algoritmo
• Comparação dos três métodos