Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Dijkstra - Coggle Diagram
Algoritmo de Dijkstra
Aplicações
amplamente usados em
planejamento de transporte
roteamento de pacotes em comunicações
outras aplicações
caminhos mais curtos em redes sociais
reconhecimento de fala
robótica
programação da tripulação de companhias aéreas
Algoritmo
passos
Primeiro encontra o caminho mais curto em relação ao
source
para o próximo vértice
depois o para p vértice seguinte , e assim por diante
o source junto com as arestas formam uma subarvores T
como as arestas não tem pesos negativo, o próximo vértice mais próximo do source é um dos vértices adjacentes de T
o conjunto de vértices adjacentes a T são chamados de
fringe
vértices
para identificar o próximo vértices, é realizado a soma da distancias e escolhido o vértices que tem a menor distancia
para facilitar as operações temos dois rótulos
d indica o comprimento do caminho mais curto do source até o vértice encontrado
quando um vértice é adicionado, d é o caminho mais curto do source até ele
rótulo pai, liga o vértices atual ao o anterior, ou seja, o pai da arvore que está sendo construída
os rótulos facilitam achar o próximo vértice mais próximo U*
com o vértice U* identificado para ser adicionado a árvore, realizamos duas operações
Mover U* para o conjunto vértices na árvore
Atualizar os rótulos dos outros os
fringe
vértices
Encontra os caminhos mais curtos na ordem de suas distancias
single-source shortest-paths problem
para determinando vértice(
source
) em grafo ponderado, encontrar os caminhos mais curtos para todos os outros vértices
Eficiência
implementado em Lista de prioridade
com matriz
Θ(|V²|)
com Lista
O(|E| log|V| )
Pode ser aplicado em grafos não direcionados e direcionados apenas com pesos não negativos