Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra's Algorithm, Aplicabilidade - Coggle Diagram
Dijkstra's Algorithm
Busca-se uma familia de caminhos de mesma fonte para diferentes vertices no grafo, esses caminhos podem ter arestas em comum
Em um grafo ponderado conectado dado um vertice chamado fonte acha-se o caminho mais curto até todos os outros vertices
Algoritmo
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
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
Esses 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
Para facilitar as operações do algoritmo, rotulamos cada vértice
com dois rótulos
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
-
-
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.
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.
-
-
-
Como na maioria das aplicações essa condição é satisfeita a
limitação não influencia na popularidade do algoritmo
-