Algoritmo de Dijkstra con una cola de prioridad

El algoritmo de Dijkstra encuentra la ruta más corta desde un único nodo de origen hasta todos los demás nodos de un grafo ponderado con pesos no negativos en las aristas. Funciona procesando los nodos de forma voraz, en orden de su mejor distancia conocida actual: siempre expande el nodo no visitado más cercano. La estructura de datos clave es un min-heap (cola de prioridad), que recupera de forma eficiente el nodo con la distancia más pequeña.

Algoritmo de Dijkstra: (1) Inicialice dist[source] = 0 y dist[all others] = inf. (2) Inserte (0, source) en un min-heap. (3) Extraiga el nodo u con la distancia más pequeña. Si ya se ha visitado con una distancia menor, omítalo. (4) Para cada vecino v de u: si dist[u] + weight(u,v) < dist[v], actualice dist[v] e inserte (dist[v], v) en el heap. (5) Repita hasta que el heap esté vacío.

heapq de Python implementa un min-heap. Representamos el grafo como una lista de adyacencia: graph[u] = [(v, weight), ...]. El heap almacena tuplas (distance, node). Utilizamos un conjunto visited para omitir las entradas obsoletas del heap: entradas insertadas antes de encontrar una ruta mejor.

Considere un grafo con 5 nodos y las aristas: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Las rutas más cortas desde el nodo 0 son: hasta 1 pasando por 0→2→1, con coste 3; hasta 2, con coste 1; hasta 3 pasando por 0→2→1→3, con coste 4; y hasta 4 pasando por 0→2→1→3→4, con coste 7. Dijkstra encuentra todas estas rutas en una sola pasada, no solo la ruta hasta un destino concreto.

La corrección de Dijkstra se basa en que, una vez que se extrae un nodo del montículo mínimo, su distancia es definitiva. Esto solo se cumple si los pesos de las aristas no son negativos. Con una arista negativa u→v de peso -5, después de visitar v podríamos encontrar un camino más corto que pase por u, pero v ya está marcado como visitado. Una sola arista negativa puede invalidar todos los cálculos de distancias posteriores.

Este problema añade una restricción: como máximo k escalas. Dijkstra estándar no gestiona de forma nativa el recuento de pasos. Solución: ampliar el estado a (cost, node, stops_remaining). Utilice Dijkstra con esta tupla de 3 elementos o Bellman-Ford con k+1 pasadas de relajación. El Dijkstra modificado se detiene cuando stops_remaining llega a 0, lo que impide realizar más saltos.

Con un montículo binario, Dijkstra se ejecuta en tiempo O((V + E) log V): cada vértice se extrae una vez (V extracciones), cada arista puede provocar una inserción (E inserciones) y cada operación del montículo cuesta O(log V). Con un montículo de Fibonacci, el límite mejora a O(E + V log V), pero el heapq de Python es un montículo binario. En grafos dispersos (E ≈ V), la versión con montículo binario es O(V log V); en grafos densos (E ≈ V²) es O(V² log V).

Para recuperar el camino real (no solo las distancias), mantenga una matriz prev: al actualizar dist[v], establezca prev[v] = u. Cuando el algoritmo termine, reconstruya el camino desde el origen hasta el destino recorriéndolo hacia atrás: comience en dst, siga los punteros de prev hasta source e invierta el resultado.

Cuando los nodos son cadenas o enteros no contiguos, utilice un defaultdict(list) para la lista de adyacencia y un dict normal para las distancias. Esto es habitual en problemas de LeetCode como Network Delay Time, donde los nodos están etiquetados del 1 al n. Recuerde utilizar dist = {node: inf for node in all_nodes} y comprobar si hay nodos inalcanzables después del algoritmo.

Para grafos no ponderados, BFS encuentra los caminos más cortos en O(V + E), más rápido que Dijkstra, que cuesta O((V+E) log V). Dijkstra generaliza BFS a grafos ponderados mediante una cola de prioridad en lugar de una cola FIFO normal. Cuando todos los pesos de las aristas son iguales, Dijkstra se reduce a BFS. Elija BFS para grafos no ponderados, Dijkstra para pesos no negativos y Bellman-Ford para pesos negativos.

La implementación de Dijkstra de los libros de texto utiliza una cola de prioridad con decrease-key: cuando mejora la distancia de un nodo, actualiza su prioridad in situ. Esto requiere un montículo de Fibonacci para O(E + V log V), pero es difícil de implementar. El enfoque de eliminación diferida que se utiliza en entrevistas inserta una nueva entrada y omite las extracciones obsoletas; es más sencillo y solo añade una sobrecarga constante. En Python, la eliminación diferida con heapq es la implementación estándar para entrevistas.

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección aprendió que: Dijkstra utiliza un montículo mínimo para procesar de forma voraz los nodos en orden de su mejor distancia actual, se ejecuta en O((V+E) log V) y falla con aristas de peso negativo y las entradas obsoletas del montículo se gestionan comprobando un conjunto de nodos visitados al extraerlas. A continuación veremos Bellman-Ford, que gestiona pesos negativos mediante n-1 pasadas de relajación.