Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra's Algorithm - Coggle Diagram
Dijkstra's Algorithm
single source shortest paph problem
em um grafo conectado com peso não negativo, ache o menor caminho de um vértice v para todos os outros
vértice v = "source"
pré requisitos
Grafos com pesos não negativos
pode ser direcionado ou não
passo a passo
acha o caminho mais curto para o vértice mais próximo
procura o segundo mais próximo...
antes da iteração n° i o algoritmo já achou a n° ( i-1)
os vértices, as arestas de menor caminho e o vértice "source/fonte" formam uma subárvore "Ti"
Fringe vertex
conjunto de vértices adjacentes a "Ti"
para achar o próximo vértice o algoritmo passa sobre todos os "fringe vertex"
a(v, u) + Dv = soma
a(v, u) = aresta da v(vértice da árvore) até u(fringe)
D(v) = menor distância da "source" até v
a menor das somas é selecionada
seleciona o u de menor caminho e move para a subárvore (u*)
para cada vértice verifica-se se o caminho passando por u* é mais curto que o caminho "d" atual
se for atualiza-se os "labels"
Labels
next-to-last
o pai do vértice na árvore "Ti"
numerical d
comprimento do menor caminho
time efficiency
com "weight matrix" e "unordered arrays"
com "adjacent lists" e min-heap
mais rápido