07_caminho_minimo_dijkstra

Prévia do material em texto

Teoria dos Grafos 
 
Caminho mínimo: algoritmo de Dijkstra 
Problema do caminho mínimo 
• Dados 
– Grafo direcionado G=(V,E) 
– Distâncias w(i,j) associadas a cada aresta (i,j) 
 
• Objetivo 
– Encontrar o caminho mínimo (mais curto) de s a t 
 
• Observações 
– O comprimento de um caminho é igual à soma das 
distâncias das arestas desse caminho 
– A distância de cada aresta pode ter várias 
interpretações 
 
Problema do caminho mínimo: exemplo 
Problema do caminho mínimo: aplicações 
Problema do caminho mínimo: aplicações 
Problema do caminho mínimo: variações 
• Quais vértices? 
– Origem-destino: de um vértice para outro vértice 
– Origem/fonte única: de um vértice para todos os outros 
– Todos os pares: entre todos os pares de vértices 
 
• Restrições nos pesos das arestas? 
– Arestas não negativas 
– Pesos arbitrários 
 
• Ciclos? 
– Sem ciclos direcionados 
– Sem ciclos “negativos” 
 
Problema do caminho mínimo 
Algoritmo de Djikstra 
• Quais vértices? 
– Origem-destino: de um vértice para outro vértice 
– Origem/fonte única: de um vértice para todos os outros 
– Todos os pares: entre todos os pares de vértices 
 
• Restrições nos pesos das arestas? 
– Arestas não “negativas” 
– Pesos arbitrários 
 
• Ciclos? 
– Sem ciclos direcionados 
– Sem ciclos “negativos” 
 
Problema do caminho mínimo 
Algoritmo de Djikstra 
• Para cada vértice 𝑣 ∈ 𝑉[𝐺] , mantemos duas 
informações importantes para o algoritmo, 
armazenadas em dois vetores d e 𝜋: 
 
– d[v]: distância mínima do vértice origem para v 
 
– 𝝅[v]: predecessor do vértice v 
Problema do caminho mínimo 
Algoritmo de Djikstra 
Problema do caminho mínimo 
Algoritmo de Djikstra - relaxação 
Problema do caminho mínimo 
Algoritmo de Djikstra: ideia principal 
1. O algoritmo mantém um conjunto S de vértices 
cujas distâncias finais de caminho já foram 
determinadas 
 
2. Repetidamente, o vértice u de V \ S que tem o 
menor caminho mínimo até então é selecionado 
 
3. O vértice u é adicionado a S 
 
4. Todas as arestas que saem de u são relaxadas 
Problema do caminho mínimo 
Algoritmo de Djikstra 
Problema do caminho mínimo 
Algoritmo de Djikstra: exemplo 
• Demonstração de Sedgewick (material extra) 
Problema do caminho mínimo 
Algoritmo de Djikstra: análise 
• Qual a complexidade do algoritmo de Dijkstra? 
– Depende da implementação da fila de prioridade Q 
• Operações executadas na fila de prioridade: 
– |V| insert, |V| delete-min, |E| decrease-key 
 
Referências 
• Introduction to Algorithms, 3ª Ed., Cormen 
• Algorithms, 4ª Ed., Robert Sedgewick and 
Kevin Wayne.