Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo Djikstra - Coggle Diagram
Algoritmo Djikstra
Problema dos caminhos mais curtos para todos os vértices de um grafo ponderado partindo de um vértice inicial
Quer como resposta uma família de caminhos, com cada um partindo do vértice inicial em direção a algum outro vértice no grafo
Diferente de perguntar qual o caminho mais curto partindo de um vértice inicial e passando por todos os outros vértices
Aplicável tanto para grafos dirigidos quanto para não-dirigidos, mas apenas com pesos não-negativos
-
-
-
Eficiência temporal
Depende das estruturas de dados usadas para implementar a fila de prioridade e para representar o grafo
Está em \(\Theta(|V|^2)\) para grafos representados como uma matriz ponderada e para a fila de prioridade como arrays não ordenados
Está em \(\Theta(|E|\log|V|)\) para grafos representados como uma lista de adjacência e filas de prioridade como uma heap mínima