Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo Dijkstra - Coggle Diagram
Algoritmo Dijkstra
É o melhor algoritmo para o problema de caminho mais curto de fonte única, onde, para um dado vértice chamado fonte em um grafo conectado com pesos, são encontrados os menores caminhos para todos os outros vértices.
O problema de caminho mais curto de fonte única pede por uma família de caminhos, cada um ligando a fonte à um vértice diferente, porém com arestas em comum.
O algoritmo Dijkstra é aplicável somente a grafos direcionados e não-direcionados com pesos não-negativos.
O algoritmo Dijkstra encontra os menores caminhos para os vértices de um grafo pela ordem de distância da sua fonte.
Primeiro ele encontra o menor caminho da fonte para um vértice próximo a fonte, e então procura o segundo mais perto, e por assim vai.
Em geral, antes da sua iteração i começar, o algoritmo já identificou os menores caminhos
para i - 1 outros vértices perto da fonte.
Esses vértices, a fonte, e as arestas dos menores caminhos que levam a eles formam a sub-árvore Tᵢ do dado grafo.
Já que todos os pesos das arestas são não-negativos, o próximo vértice mais perto da fonte pode ser encontrado entre os vértices adjacentes aos vértices de Tᵢ.
O conjunto de vértices adjacentes aos vértices em Tᵢ, podem ser chamados de "fringe vertices", eles são os candidatos dos quais o Dijkstra seleciona o próximo vértice mais perto da fonte.
Para identificar o vértice i mais perto, o algoritmo computa, para cada fringe vertex u, a soma da distância para o vértice mais próximo v, e o tamanho dᵥ do menor caminho da fonte até v, e então, seleciona o vértice com a menor soma.
Para facilitar as operações do algoritmo, cada vértice recebe dois rótulos.
O rótulo numérico d indica o tamanho do menor caminho da fonte para este vértice encontrado pelo algoritmo; quando um vértice é adicionado à árvore, d indica o menor caminho da fonte para este vértice.
-
Com esses rótulos, encontrar o vértice mais próximo u* se transforma em uma simples tarefa de encontrar o fringe vertex com o menor valor
d.
Depois que o vértice u* a ser adicionado à árvore é encontrado, são realizadas duas operações:
-
2. Para cada fringe vertex u remanescente que está conectado a u* por uma aresta de peso w(u*, u) ao qual dᵤ* + w(u*, u) < dᵤ, os rótulos de u por u* e dᵤ* + w(u*, u) são atualizados respectivamente.
A eficiência temporal do algoritmo Dijkstra depende das estruturas de dados usadas para implementar a fila de prioridade e para representar o grafo de entrada.
Então ele está em Θ(|V²|) para grafos representados pela sua matriz de peso e sua fila de prioridade implementada por um array desordenado.
E está em O(|E| log |V|) para grafos representados por listas de adjacência e suas filas de prioridade implementadas como min-heap.