Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos, for every vertex v in V, dv ← ∞; pv ← null, Insert(Q, v, dv)…
Algoritmos
Algortmo de Dijkstra
-
Este algoritmo é aplicável para gráficos não direcionados e direcionados com pesos não negativos apenas.
Input
Um gráfico conectado ponderado G = V, E com pesos não negativos.
Output
O comprimento Dv de um caminho mais curto de s para v e seu penúltimo vértice Pv para cada vértice v em V.
Eficiencia temporal
A eficiência temporal do algoritmo de Dijkstra depende das estruturas de dados usadas
para implementar a fila de prioridade e para representar um gráfico de entrada em si.
-
-
-
Insert(Q, v, dv) //initialize vertex priority in the priority queue
ds ← 0; Decrease(Q, s, ds) //update priority of s with ds
-
-
-
-
-
-
du ← du∗ + w(u∗, u); pu ← u∗
-