Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra’s Algorithm - Coggle Diagram
Dijkstra’s Algorithm
Aplicação
Planejamento de Transporte
Roteamento de Pacotes em Redes de Comunicação
Robótica
Internet
pathfindinng
Path-Planning
Conceito
Encontra o caminha mais curto para o vertice de um grago em ordem de distancia para uma determinada fonte
Passos
Encontra caminha mais curto da fonte até o vertice mais próximo
Depois até o segundo mais próximo
Assim por Diante
A "fonte" e as arestas dos caminhos mais curtos formam uma subárvore Ti
Como os Pesos Não são Negativos
O próximo vertice mais perto da fonte se encontra entre os vertices adjacentes ao vertices de Ti
Esses Vertices Adjacentes são chamados "Fringe Vertices"
1 more item...
Facilitar as operações
Se cria dois rotulos
Indica o comprimento do caminho mais curto da fonte até este vertice(até agora)
Achar o próximo vertice mais proximo se torna fácil
Laços são quebrados mais facilmente
Indica o Pai do vértice na árvore que esta sendo construída
Identificar um vertice a ser adicionado na arvore
operações
Mova o vertice U do fringe para o conjunto de vértices da árvore
Para cada vértice do fringe restante que está conectado a U
Atualizar os rotulos
Se du∗ + w(u∗, u) < d
Tempo de eficiencia
Depende da estrutura de dados utilizada para implementar o heap
Depende também de como você representa o grapho
Resolve o problema do menor caminho
Dos vértices para os outros vertices
Grafo não direcionado com pesos não negativos
Não resolve o problema de achar o menor caminho
Que comece de um vértice e visite todos os outros vértices