Complejidad de Dijkstra (Big-O)
El algoritmo de Dijkstra calcula caminos más cortos desde un origen en grafos con aristas no negativas en O((V + E) log V) usando un heap binario, con O(V) espacio.
Abrir la herramienta DevRef Hub →Datos clave
| Tiempo (heap binario) | O((V + E) log V) |
|---|---|
| Espacio | O(V) |
| Restricción | Aristas no negativas |
| Tipo | Camino más corto de origen único |
Preguntas frecuentes
¿Cuál es la complejidad de Dijkstra?
O((V + E) log V) con una cola de prioridad de heap binario.
¿Por qué las aristas deben ser no negativas?
Los pesos negativos rompen la suposición greedy; usa Bellman-Ford.
Páginas relacionadas
Big-O de Dijkstra forma parte de DevRef Hub en GOAT Lab: una referencia gratuita que puedes usar sin registrarte y que funciona sin conexión. Abre la herramienta de arriba para cualquier valor.
Parte de GOAT Lab — 26 herramientas gratuitas en el navegador para ciencia, ingeniería y desarrollo. Sin registro.