Algoritmo de Dijkstra

Prévia do material em texto

Grafos
Professor: Alexandre
Algoritmo de Dijkstra
◼ Edsger Wybe Dijkstra professor e
pesquisador na área de Ciência da
Computação;
◼ Recebeu Turing Award 1972 mais renomado
prêmio da Computação;
◼ Contribuições fundamentais em ling. de
programação e verificação formal
◼ Algoritmo de Dijkstra utilizado em vários
sistemas,tais como: redes, GPS, entre outros.
Algoritmo de Dijkstra
◼ É um dos algoritmos que calcula o caminho
de custo mínimo entre vértices de um grafo.
Escolhido um vértice como raiz da busca, este
algoritmo calcula o custo mínimo deste vértice
para todos os demais vértices do grafo. Ele é
bastante simples e com um bom nível de
performance.
◼ Ele não garante, contudo, a exatidão da
solução caso haja a presença de arcos com
valores negativos.
Algoritmo de Dijkstra
◼ É um dos algoritmos que calcula o caminho
de custo mínimo entre vértices de um grafo.
Escolhido um vértice como raiz da busca, este
algoritmo calcula o custo mínimo deste vértice
para todos os demais vértices do grafo. Ele é
bastante simples e com um bom nível de
performance.
◼ Ele não garante, contudo, a exatidão da
solução caso haja a presença de arcos com
valores negativos.
Algoritmo de Dijkstra
◼ Grafos com pesos
❑ Anotar arestas do grafo com “intensidade” do
relacionamento
❑ peso da aresta (weight)
❑ função w(e) retorna peso da aresta
Algoritmo de Dijkstra
◼ Comprimento de um caminho
❑ soma dos pesos das arestas que definem o
caminho
◼ Distância
❑ comprimento do menor caminho simples entre dois
vértices
Algoritmo de Dijkstra
◼ Algoritmo: Seja G(V,A) um grafo orientado e s um vértice de G:
◼ Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da
busca) e infinito às demais estimativas;
◼ Atribua um valor qualquer aos precedentes (o precedente de um
vértice t é o vértice que precede t no caminho de custo mínimo
de s para t);
◼ Enquanto houver vértice aberto:
❑ seja k um vértice ainda aberto cuja estimativa seja a menor dentre
todos os vértices abertos;
❑ feche o vértice k
❑ Para todo vértice j ainda aberto que seja sucessor de k faça:
◼ some a estimativa do vértice k com o custo do arco que
une k a j;
◼ caso esta soma seja melhor que a estimativa anterior para o
vértice j, substitua-a e anote k como precedente de j.
Algoritmo de Dijkstra
1.Dijkstra(G, s)
2.Para cada vértice v
3. dist[v] = infinito
4.Define conjunto S = 0 // vazio
5.dist[s] = 0
6.Enquanto S != V
7. Selecione u em V-S, tal que dist[u] é mínima
8. Adicione u em S
9. Para cada vizinho v de u faça
10. Se dist[v] > dist[u] + w((u,v)) então
11. dist[v] = dist[u] + w((u,v))
Algoritmo de Dijkstra
◼ Exemplo de execução:
❑ Calcular a distância dos nós com relação ao nó “A”
❑ Inicializar os custos dos vértices, o vértice inicial tem o valor
zero, pois não tem custo. Os outros vértices recebem valor
infinito representando que ainda não foram calculados custos.
Algoritmo de Dijkstra
◼ Exemplo de execução:
❑ Atualiza o peso dos nós adjacentes ao nó A
Algoritmo de Dijkstra
◼ Exemplo de execução:
❑ Escolhe o caminho de menor valor, no caso: A-B
❑ Atualiza o valor do nó adjacente (E) com o peso do B mais o
valor da aresta B-E. O nó 3 é marcado como avaliado.
Algoritmo de Dijkstra
◼ Exemplo de execução:
❑ Os nós C e D, adjacentes a A não foram avaliados, encontrar o
de menor valor, no caso: D
Algoritmo de Dijkstra
◼ Exemplo de execução:
❑ Atualizar o valor dos nós adjacentes ao D: C e E.
❑ Escolhe o menor nó de menor valor adjacente ao D: C ou E.
❑ Define o nó C como próximo.
Algoritmo de Dijkstra
◼ Exemplo de execução:
❑ Atualizar o valor dos nós adjacentes ao C: E.
❑ O valor calculado é maior do que o valor do nó, não devemos
atualizar (5 + 9 > 10). Mantém o valor 10 ao invés do 14.
Algoritmo de Dijkstra
◼ Ao término da execução do algoritmo, os nós ficam
com a marcação da sua distância com relação ao nó
A.
◼ Exemplo:
Algoritmo de Dijkstra