Time and Space Complexity
Lección 7 de 9 del curso Algoritmo de Dijkstra - Algoritmos de grafos de Coddy.
Complejidad Temporal:
- O(V2 + V*E) tal como está escrito aquí (cada una de las V rondas escanea los vértices para encontrar el mínimo y escanea las aristas para relajar). Con un montículo binario y una lista de adyacencia, mejora a O((V + E) log V).
Complejidad Espacial:
- O(V) para los arreglos de distancia y visitados (más las aristas de entrada).
Resumen:
- Dijkstra encuentra las distancias más cortas desde una única fuente para pesos no negativos, finalizando de forma voraz el vértice más cercano y relajando sus aristas.
- No funciona con aristas negativas; use Bellman-Ford para esos casos.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Algoritmo de Dijkstra - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity