Please enable JavaScript.
Coggle requires JavaScript to display documents.
333-337 Algoritmo de Dijkstra - Coggle Diagram
333-337 Algoritmo de Dijkstra
Caminho mais curto partindo de uma fonte singular
Em um grafo ponderado conectado dado um vertice chamado fonte acha-se o caminho mais curto até todos os outros vertices
Busca-se uma familia de caminhos de mesma fonte para diferentes vertices no grafo, esses caminhos podem ter arestas em comum
Aplicabilidade
Grafos direcionados com pesos não negativos
Grafos não direcionados com pesos não negativos
Como na maioria das aplicações essa condição é satisfeita a limitação não influencia na popularidade do algoritmo
Algoritmo
Acha os menores caminhos até os vertices do grafo em função da distancia de uma fonte dada
Primeiro acha-se o menor caminho da fonte pra um vertice próximo depois para o segundo próximo e assim em diante
Geralmente antes da iésima iteração já identificou-se os caminhos mais curtos para os i-1 outros vertices proximos à fonte
Eses vértices, a fonte e as arestas dos caminhos mais curtos que conduzem a eles a partir da fonte formam uma subárvore Ti do dado grafo
O próximo vertice mais próximo da fonte pode ser encontrado entre os vértices adjacentes aos vértices de Ti, os vertices de margem, os quais são os candidatos a partir dos quais o algoritmo de Dijkstra seleciona o próximo vértice mais próximo da fonte.
Para identificar o iésimo vertice mais próximo o algoritmo calcula a soma da distancia de um vertice u para o vertice mais proximo v da arvore e o comprimento dv do caminho mais curto da fonte para v, em seguida seleciona-se o vertice com a menor soma
Para facilitar as operações do algoritmo, rotulamos cada vértice com dois rótulos.
O rótulo numérico d indica o comprimento do caminho mais curto da fonte até este vértice encontrado pelo algoritmo até o momento atual; quando um vértice é adicionado à árvore, d indica o comprimento do caminho mais curto da fonte até aquele vértice.
O outro rótulo indica o nome do pai do vértice na árvore que está sendo construída.
Com tal rotulagem, encontrando o próximo vértice mais próximo u* torna-se uma tarefa simples de encontrar um vértice de margem com o menor valor d. Os laços podem ser quebrados arbitrariamente.
Depois de identificar um vertice u* a ser adicionado na arvore precisa-se ser operadas duas operações
Mova u* da margem ao conjunto de vértices da árvore.
Para cada vértice de margem restante u que está conectado a u* por uma borda de peso w (u ∗ , u) tal que du ∗ + w (u ∗ , u) <du, atualize os rótulos de u por u ∗ e du ∗ + w (u ∗ , u), respectivamente.