Please enable JavaScript.
Coggle requires JavaScript to display documents.
DIJKSTRA - Coggle Diagram
DIJKSTRA
-
Após identificarmos um vértice u∗ a ser adicionado à árvore, precisamos realizar
duas operações:
-
Para cada vértice restante da franja u que está conectado a u∗ por uma aresta de peso w(u∗, u) tal que du∗ + w(u∗, u) < du, atualizar os rótulos de u por u∗
e du∗ + w(u∗, u), respectivamente.
Para um dado vértice chamado de fonte em um grafo conectado ponderado, encontrar caminhos mais curtos para todos seus outros vértices.
O problema dos caminhos mais curtos de fonte única pede uma família de caminhos, cada um levando da fonte para um vértice diferente no grafo, embora alguns caminhos possam, claro, ter arestas em comum.
Este algoritmo é aplicável para grafos não direcionados e direcionados apenas com pesos não negativos.
Como na maioria das aplicações essa condição é satisfeita, a limitação não prejudicou a popularidade do algoritmo de Dijkstra.
O algoritmo de Dijkstra encontra os caminhos mais curtos para os vértices de um grafo em ordem de sua distância de uma determinada fonte.
Primeiro, ele encontra o caminho mais curto da fonte para um vértice mais próximo a ele, depois para um segundo mais próximo, e assim por diante.
Em geral, antes do início da iteração, o algoritmo já identificou os caminhos mais curtos para i − 1 outros vértices mais próximos da fonte.
Esses vértices, a fonte e as arestas dos caminhos mais curtos que levam a eles a partir da fonte formam uma subárvore Ti do dado grafo.
Como todos os pesos das arestas são não negativos, o próximo vértice mais próximo da fonte pode ser encontrado entre os vértices adjacentes aos vértices de Ti.
O conjunto de vértices adjacentes aos vértices em Ti pode ser referido como “franja vértices”; eles 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 vértice mais próximo, o algoritmo calcula, para cada vértice de franja u, a soma da distância ao vértice da árvore mais próximo v (dado pelo peso do aresta (v, u)) e o comprimento dv do caminho mais curto da fonte para v (anteriormente determinado pelo algoritmo) e então seleciona o vértice com o menor soma.
O fato de que basta comparar os comprimentos de tais caminhos especiais é o visão central do algoritmo de Dijkstra.
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 para este vértice encontrado pelo algoritmo até agora;
Quando um vértice é adicionado à árvore, d indica o comprimento do caminho mais curto da fonte para esse vértice.
O outro rótulo indica o nome do penúltimo vértice em tal caminho, ou seja, o pai do vértice na árvore que está sendo construída.
Com tal rotulagem, encontrar o vértice mais próximo u∗ torna-se uma tarefa simples de encontrar um vértice da franja com o menor valor de d. Laços podem ser quebrados arbitrariamente.
O algoritmo de Dijkstra compara comprimentos de caminho e, portanto, deve adicionar pesos.