Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM12 - Coggle Diagram
MM12
Dijkstra’s Algorithm
-
Algoritmo usado para encontrar caminhos mais curtos de fonte única: para um determinado vértice chamado fonte em um graph conectado ponderado, encontre os caminhos mais curtos para todos os seus outros vértices
Encontra os caminhos mais curto para os vértices de um graph na ordem de sua distância a uma determinada fonte
Primeiro, ele encontra o caminho mais curto da origem para um vértice mais próximo dele, depois para um segundo mais próximo e assim por diante
Em geral, antes de sua i-ésima interação começar, o algoritmo já identificou os caminhos mais curtos para i-1 outros vértices mais proximos do ponto
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 graph dado
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
-
Para identificar o i-ésimo vértice mais próximo, o algoritmo calcula, para cada vértice marginal u, a soma da distância até a arvore mais próxima vértice v (dado pelo peso da aresta (v, u)) e o comprimento dv do caminho mais curto da fonte até v (previamente determinado pelo algoritmo) e então seleciona o vértice com a menor soma
O fato de ser suficiente comparar os comprimentos de tais caminhos especiais é o insight central do algoritmo de Dijkstra
Para facilitar, rotulamos cada vértice com dois rótulos
O rotulo número d indica o comprimento do caminho mais curto da origem até o vértice encontrado pelo algoritmo até o momento
Quando um vértice é adicionado a arvore, d indica o comprimento do caminho mais curto da origem até aquele vértice
O outro rotulo indica o nome do penúltimo vértice nesse caminho, ou seja, o pai do vértice na árvore que está sendo construída
Com tal rotulagem, encontrar o próximo vértice mais próximo u* torna-se uma tarefa simples de encontrar um vértice marginal com o menor valor d. Os empates podem ser resolvidos arbitrariamente
Depois de identificar um vértice u* a ser adicionado a árvore, precisamos realizar duas operações:
-
Para cada vértice u de franja restante que esta conectado a u por uma aresta 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