Overview
El algoritmo de Dijkstra encuentra el camino más corto desde un nodo de origen a todos los demás en grafos con pesos no negativos.
Analogy
Como navegar en GPS: siempre expandes el destino alcanzable más barato siguiente, hasta haber encontrado el camino más corto a todo.
Step-by-step
- Inicializa distancias: origen=0, todos los demás=∞
- Usa una cola de prioridad (min-heap)
- Extrae el nodo con distancia mínima
- Actualiza vecinos si se encuentra un camino más corto
- Repite hasta que todos los nodos estén procesados
Visual
A→B(1), A→C(4), B→C(2)
Dijkstra desde A:
dist[A]=0, dist[B]=1, dist[C]=3
Common mistakes
- Usar con pesos negativos → resultados incorrectos (usa Bellman-Ford)
- No actualizar el heap cuando se encuentra un camino más corto
Practice questions
- Encuentra el camino más corto en un mapa de ciudad
- Implementa con reconstrucción del camino usando el array de previo
Time
O((V+E) log V) con heap binario
Space
O(V) para el heap y el array de distancias