Dijkstra con un heap
Encuentre caminos mínimos greedy en aristas no negativas
Dijkstra con un heap es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El problema del camino más corto
Quiere encontrar la ruta de menor costo desde un nodo hasta todos los demás. Dijkstra resuelve este problema cuando todos los pesos de las aristas son cero o positivos.
La idea voraz
Dijkstra es voraz: siempre expande el nodo no visitado con la menor distancia conocida, confiando en que esa distancia es definitiva.
Por qué usar un min-heap
Para obtener rápidamente el nodo más cercano, necesita un min-heap. Este le proporciona la menor distancia en tiempo log n, en lugar de obligarle a hacer un recorrido lento.
import heapqComience con las distancias
Establezca todas las distancias en infinito y luego establezca la del origen en cero. Los nodos no alcanzados simplemente permanecen en infinito para siempre.
dist = [float('inf')] * n
dist[src] = 0Inicialice el heap
Inserte el origen como una tupla de (distancia, nodo). Colocar primero la distancia permite que el heap ordene automáticamente las entradas por costo.
pq = [(0, src)]Extraiga el nodo más cercano
En cada iteración, haga pop del menor (d, u). Esa d es la distancia más corta hasta u, por lo que su procesamiento termina una vez que se extrae.
d, u = heapq.heappop(pq)Omita las entradas obsoletas
Es posible que un nodo permanezca en el heap con una distancia antigua y mayor. Omítalo cuando d sea peor que la distancia almacenada.
if d > dist[u]:
continueRelaje los vecinos
La relajación consiste en intentar mejorar la distancia de un vecino: si pasar por u es más barato, actualice su distancia e insértelo.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))El truco de la eliminación diferida
Los heaps de Python no pueden actualizar una clave, así que se insertan duplicados y se ignoran los obsoletos. Este estilo diferido mantiene el código breve y rápido.
El tiempo de ejecución
Con un heap binario, Dijkstra se ejecuta en O((V + E) log V). Esto permite manejar fácilmente grafos con cientos de miles de aristas.
Preste atención a los pesos de las aristas
Dijkstra falla con aristas negativas, ya que una distancia extraída podría no ser definitiva. En esos casos, use Bellman-Ford.
Comprobación rápida
Extrae (d, u), pero d es mayor que dist[u]. ¿Qué debe hacer?
Repaso: Dijkstra con un heap
Inicializa las distancias, inserta (dist, node), extrae el nodo más cercano, omite las extracciones obsoletas y relaja los vecinos. Ese es Dijkstra en O((V+E) log V). 🚀
Preguntas frecuentes
¿La lección «Dijkstra con un heap» es gratis?
Sí — el texto completo de «Dijkstra con un heap» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Dijkstra con un heap»?
Encuentre caminos mínimos greedy en aristas no negativas Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Dijkstra con un heap»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Dijkstra con un heap
- BFS 0-1 con una deque
- Bellman-Ford y aristas negativas
- Floyd-Warshall para todos los pares