Time and Space Complexity
Lição 7 de 9 do curso Algoritmo de Dijkstra - Algoritmos de Grafos da Coddy.
Complexidade de Tempo:
- O(V2 + V*E) como escrito aqui (cada uma das V rodadas varre os vértices para encontrar o mínimo e varre as arestas para relaxar). Com um heap binário e uma lista de adjacência, melhora para O((V + E) log V).
Complexidade de Espaço:
- O(V) para os arrays de distância e visitados (além das arestas de entrada).
Resumo:
- Dijkstra encontra as distâncias mais curtas de fonte única para pesos não negativos, finalizando de forma gulosa o vértice mais próximo e relaxando suas arestas.
- Não funciona com arestas negativas; use Bellman-Ford para esses casos.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Dijkstra - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity