Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
(9) Greedy Technique (333 - 337)
(9.3) Algoritmo de Dijkstra
Single-source shortest paths
Grafo conectado de pesos
Achar os menores caminhos entre vértices
Aplicações
Planejamento de transporte
Networks de comunicação
Robótica
Compiladores
Etc...
Especificidades
Grafo direcionado
Grafo não direcionado
Pesos não negativos
Método de atuação
Menor caminho entre vértices em ordem da distância de uma fonte
Sabe os i-ésimos nós perto da fonte
Como não há peso negativo, o próximo nó será adjacente a um dos anteriores
"Fringe vertices"
Algoritmo calcula o nós mais perto
dw + weight(w, u) < du
Uso de filas de prioridade
Eficiência
Matriz de pesos + fila de prioridade como array não ordenado
θ(|V|²)
Melhor para grafos densos
Listas de Adjacência + heap mínima
O(|E| log |V|)
Melhor para grafos espaçados
Heap de Fibonacci garante eficiência melhor