Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra’s algorithm, “vértices marginais”;-> O conjunto de vértices…
Dijkstra’s algorithm
-
-
encontra os caminhos mais curtos para os vértices de um gráfico na ordem de sua distância de uma determinada fonte.
Primeiro, ele encontra o caminho mais curto da origem até um vértice mais próximo dela, depois até um segundo vértice mais próximo e assim por diante.
Em geral, antes de sua i-ésima iteração começar, 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 grafo 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 ao vértice v mais próximo (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 desse tipo.
Eficiência Temporal
depende das estruturas de dados usadas para implementar a fila de prioridade e para representar o próprio gráfico de entrada.
para grafos representados por sua matriz de pesos e a fila de prioridade implementada como uma matriz não ordenada.
-
Para grafos representados por suas listas de adjacências e a fila de prioridade implementada como min-heap
-
-
“vértices marginais”;-> O conjunto de vértices adjacentes aos vértices em Ti, são os candidatos a partir dos quais o algoritmo de Dijkstra seleciona o próximo vértice mais próximo da fonte.
-