Entrevista de código: Implementar el algoritmo de camino más corto de Dijkstra

Planteamiento y alcance

Se te da un grafo dirigido con n nodos etiquetados de 0 a n - 1. Cada arista es una tupla (from, to, weight). Dados source y target, devuelve un par que contenga la distancia más corta y un camino más corto desde el origen hasta el destino. Devuelve (-1, []) cuando el destino sea inalcanzable.

Para esta versión, asume 1 <= n <= 100000, 0 <= m <= 300000, que cada etiqueta de nodo es válida y 0 <= weight <= 10^9. Se permiten aristas paralelas, aristas de peso cero y bucles sobre sí mismos (self-loops). source y target son etiquetas válidas. Si son iguales, devuelve (0, [source]). Cualquier camino más corto es aceptable cuando varios tengan la misma distancia.

Por ejemplo, con las aristas (0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3) y (2, 4, 12), la respuesta de 0 a 4 es una distancia de 7 y el camino [0, 2, 1, 3, 4].

La condición de pesos no negativos forma parte del contrato del algoritmo. Un grafo ponderado no implica por sí mismo usar Dijkstra: un grafo no ponderado favorece BFS, un DAG puede usar programación dinámica topológica, y un grafo general con aristas negativas necesita un algoritmo como Bellman-Ford.

Qué evalúa el entrevistador

La primera señal es la selección del algoritmo a partir del contrato. Dijkstra es adecuado porque los pesos de las aristas son no negativos y solo interviene un origen. Un candidato que dice “grafo ponderado significa Dijkstra” sin preguntar sobre pesos negativos ha pasado por alto la precondición decisiva.

La segunda señal es el invariante de la estructura de datos. Una matriz de adyacencia requeriría un espacio de O(V^2), lo cual no es adecuado para hasta 100,000 nodos. Una lista de adyacencia almacena solo la información V + E que utiliza el recorrido. Un min-heap recupera el nodo no asentado con la menor distancia descubierta.

La tercera señal es cómo se representan las disminuciones de distancia. El heapq de Python no actualiza un elemento arbitrario in situ. La solución práctica inserta un nuevo par (distance, node) y más tarde omite un par antiguo cuando su distancia ya no es igual a distances[node]. Este detalle de eliminación perezosa (lazy deletion) es fácil de omitir y cambia tanto el razonamiento de corrección como el límite preciso de complejidad.

El entrevistador también espera una demostración, no solo código funcional. Una respuesta sólida explica por qué la primera entrada actual extraída para un nodo es definitiva, por qué los pesos no negativos hacen que ese paso voraz sea seguro, y por qué el destino puede devolverse cuando se extrae en lugar de cuando se descubre por primera vez. La reconstrucción del camino, entradas inalcanzables, aristas de peso cero, aristas paralelas, el ancho de enteros y pruebas adversarias completan la respuesta.

Preguntas para clarificar antes de responder

• ¿Pueden ser negativos los pesos de las aristas? El problema base dice que no. Si se permiten aristas negativas,

la demostración de asentamiento de Dijkstra y la salida temprana no se sostienen.

• ¿Es el grafo dirigido? Sí. Para un grafo no dirigido, añade ambas direcciones a la lista de adyacencia.
• ¿Necesitamos solo la distancia o también el camino? Esta versión necesita ambos, así que guarda un predecesor

cada vez que una relajación mejore estrictamente una distancia.

• ¿Puede haber aristas paralelas, aristas de peso cero o bucles sobre sí mismos? Sí. La relajación los maneja

sin preprocesamiento. Un bucle sobre sí mismo no negativo no puede mejorar su propio nodo.

• ¿Qué debe significar inalcanzable? Devuelve (-1, []); no lo confundas con un camino de longitud cero.
• Cuando existen varios caminos más cortos, ¿es aceptable cualquiera de ellos? Sí. La implementación actualiza un

predecesor solo ante una mejora estricta, por lo que las alternativas iguales no alteran el árbol de caminos.

• ¿Qué tan grande puede llegar a ser una distancia? Un camino simple más corto tiene como máximo n - 1 aristas, por lo que bajo los

límites establecidos está por debajo de 10^14. Los enteros en Python no tienen límite; usa un entero de 64 bits en un lenguaje de ancho fijo.

Estructura de respuesta de 30 segundos

“Construiré una lista de adyacencia y mantendré distances[v], la mejor distancia de origen a v encontrada hasta ahora. Inicializo el origen en cero y coloco (0, source) en un min-heap. Cada vez que extraigo la entrada más pequeña, la omito si está obsoleta. De lo contrario, la distancia de ese nodo es definitiva porque cada arista restante tiene un peso no negativo. Relajo cada arista saliente e inserto una nueva entrada en el heap por cada mejora estricta, registrando un predecesor para la reconstrucción del camino. Puedo detenerme cuando se extrae la entrada actual del destino. Si su distancia permanece infinita, devuelvo (-1, []); de lo contrario, sigo a los predecesores hacia atrás e invierto el camino. Con entradas perezosas en el heap, el tiempo es O((V + E) log E) y el espacio es O(V + E).”

Análisis detallado paso a paso

Comienza separando una ruta descubierta de una ruta más corta demostrada. distances[v] es un límite superior de la verdadera distancia más corta porque es infinito o la longitud de una ruta real ya encontrada. Relajar una arista u -> v con peso w evalúa si la ruta a través de u es mejor: distances[u] + w < distances[v]. Una mejora estricta actualiza tanto la distancia como previous[v].

El heap puede contener varias entradas para el mismo nodo. En el ejemplo, la arista 0 -> 1 inserta primero la distancia 4. Después de procesar el nodo 2, la ruta 0 -> 2 -> 1 mejora el nodo 1 a distancia 3 e inserta una segunda entrada. Cuando finalmente se extrae (4, 1), 4 != distances[1], por lo que está obsoleta y debe ignorarse. No se requiere la eliminación explícita de elementos del heap ni un conjunto de nodos visitados.

from heapq import heappop, heappush


def shortest_path(
    n: int,
    edges: list[tuple[int, int, int]],
    source: int,
    target: int,
) -> tuple[int, list[int]]:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for node, neighbor, weight in edges:
        if weight < 0:
            raise ValueError("Dijkstra requires non-negative edge weights")
        graph[node].append((neighbor, weight))

    distances = [float("inf")] * n
    previous = [-1] * n
    distances[source] = 0
    heap: list[tuple[int, int]] = [(0, source)]

    while heap:
        distance, node = heappop(heap)
        if distance != distances[node]:
            continue
        if node == target:
            break

        for neighbor, weight in graph[node]:
            candidate = distance + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                previous[neighbor] = node
                heappush(heap, (candidate, neighbor))

    if distances[target] == float("inf"):
        return -1, []

    path = []
    node = target
    while node != -1:
        path.append(node)
        node = previous[node]
    path.reverse()
    return int(distances[target]), path

El argumento de corrección consta de dos partes. Primero, cada valor finito en distances es la longitud de un camino real descubierto, por lo que no puede ser menor que la verdadera distancia del camino más corto. Segundo, supongamos que se extrae una entrada actual para u pero existe un camino más corto hacia u. En ese camino, toma el primer nodo que aún no ha sido asentado y llama a su predecesor x. El nodo x se asentó antes, por lo que su arista saliente fue relajada. Por lo tanto, el primer nodo no asentado recibió una clave de heap no mayor que la longitud del camino más corto hipotético hacia u. Como todos los pesos de las aristas restantes son no negativos, esa clave es menor que la clave extraída para u y debería haberse extraído primero, lo cual es una contradicción. Por lo tanto, la distancia actual extraída es definitiva.

Esta demostración también define el punto seguro de salida temprana. Detente solo después de que el destino sea extraído con una distancia actual y no obsoleta. No te detengas cuando una arista descubra por primera vez el destino: una ruta posterior puede mejorarlo. Para el grafo de ejemplo, el descubrimiento directo del nodo 4 cuesta 13, mientras que la ruta final cuesta 7.

previous[v] = u registra la última arista del camino actualmente mejor hacia v. Una vez que la distancia del destino es definitiva, seguir a los predecesores debe llegar al origen porque cada asignación de predecesor provino de una ruta real con raíz en el origen. Invertir esa cadena devuelve el camino en orden directo. Cuando el origen es igual al destino, el origen se extrae inmediatamente y la reconstrucción devuelve [source].

Construir la lista de adyacencia toma un espacio de O(V + E) y un tiempo de O(E). Cada relajación exitosa inserta una entrada en el heap, por lo que hay como máximo E inserciones de este tipo además de la entrada inicial del origen. Con duplicados perezosos, el heap puede contener O(E) entradas, lo que da un tiempo de O((V + E) log E) y un espacio total de O(V + E). Los libros de texto a menudo establecen O((V + E) log V) para un heap que admite decrease-key, o simplifican a ese límite para grafos dispersos simples. Mencionar el límite log E de la implementación perezosa es más preciso.

Prueba el contrato, no solo el caso ideal (happy path). El ejemplo debe devolver (7, [0, 2, 1, 3, 4]). Aristas paralelas y un peso cero—(0, 1, 10), (0, 1, 2), (1, 2, 0)—deberían devolver (2, [0, 1, 2]). Prueba también un destino inalcanzable, origen igual al destino, un bucle sobre sí mismo, alternativas de igual costo y una arista de peso cero. Una arista negativa debería lanzar un error explícito en lugar de producir silenciosamente una respuesta bajo una precondición incumplida.

Una pequeña prueba diferencial puede generar grafos no negativos, ejecutar esta función desde cada origen y comparar sus distancias con Bellman-Ford. Para los caminos devueltos, verifica el primer y el último nodo, verifica que cada par consecutivo sea una arista de entrada y suma los pesos de las aristas seleccionadas. Con aristas paralelas, la prueba debe asociar el paso del camino con un peso de arista coincidente en lugar de asumir que cada par de nodos tiene una sola arista.

Respuesta de muestra de alta calidad

“Primero confirmaría que todos los pesos de las aristas son no negativos, que el grafo es dirigido y que cualquier camino más corto es aceptable. Esas condiciones me permiten usar Dijkstra. Almacenaré las aristas salientes en una lista de adyacencia porque el grafo puede tener 100,000 nodos y 300,000 aristas; una matriz de adyacencia sería demasiado grande.

distances[v] comienza en infinito excepto para el origen, que comienza en cero. Un min-heap almacena los pares (distance, node) descubiertos. Cuando encuentro una ruta más corta a través del nodo actual, actualizo la distancia y el predecesor del vecino e inserto un nuevo par. Dado que heapq no tiene decrease-key arbitrario, los pares antiguos permanecen en el heap. Los detecto comparando la distancia extraída con el valor actual del arreglo y omito cualquier discrepancia.

La demostración clave es el invariante de asentamiento. Cuando una entrada actual para el nodo u es el mínimo del heap, cualquier ruta hipotética más corta contendría un primer nodo no asentado cuyo predecesor ya fue asentado. La relajación de ese predecesor habría colocado una distancia de prefijo igual o menor en el heap. Como los pesos restantes son no negativos, ese prefijo debería haberse extraído antes de u, lo cual es una contradicción. Por lo tanto, u es definitivo. Por esto puedo detenerme cuando se extrae la entrada actual del destino, pero no cuando el destino se ve por primera vez.

Si el destino permanece infinito, devuelvo (-1, []). De lo contrario, sigo los punteros de predecesores desde el destino hasta el origen y los invierto. Cada relajación exitosa crea como máximo una nueva entrada en el heap, por lo que esta implementación perezosa se ejecuta en un tiempo de O((V + E) log E) y utiliza un espacio de O(V + E). En un lenguaje de ancho fijo usaría distancias de 64 bits. Probaría entradas obsoletas, aristas paralelas y de peso cero, caminos de igual costo, origen igual al destino, entrada inalcanzable y el rechazo de una arista negativa.”

Errores comunes

• Ejecutar Dijkstra sin preguntar sobre pesos negativos → la demostración de finalización voraz falla →

Haz que los pesos no negativos sean una precondición explícita y rechaza la entrada inválida.

• Detenerse cuando el destino se relaja por primera vez → la primera ruta descubierta puede ser costosa →

Deténte solo cuando se extraiga la entrada actual del destino del heap.

• Procesar entradas obsoletas del heap → las distancias antiguas escanean repetidamente las aristas salientes → **Omite cuando

distance != distances[node].**

• Marcar un nodo como visitado cuando se inserta por primera vez → se suprime una ruta más corta posterior → **Un nodo

se asienta solo cuando se extrae su entrada mínima actual.**

• Usar una matriz de adyacencia → una entrada dispersa consume memoria de O(V^2) → **Usa una lista de adyacencia con

almacenamiento de O(V + E).**

• Actualizar predecesores en distancias iguales sin una regla de desempate → los ciclos de peso cero pueden alterar las

elecciones de camino → Usa mejora estricta cuando cualquier camino más corto sea aceptable.

• Devolver una distancia finita pero ningún contrato de camino → la implementación no satisface el planteamiento

→ Registra un predecesor en cada mejora estricta y reconstruye después de la búsqueda.

• Llamar a esta implementación con heap O(E log V) sin aclaraciones → los duplicados perezosos pueden hacer

que el tamaño del heap sea proporcional a E → **Indica O((V + E) log E), luego explica el límite convencional con decrease-key.**

• Usar una distancia de 32 bits → los caminos pueden superar aproximadamente los 2,100 millones → **Usa enteros de Python o un tipo de 64

bits.**

• Probar solo la distancia final → una cadena de predecesores mal formada pasa desapercibida → **Valida

también los extremos del camino, las aristas y el peso total sumado.**

Preguntas de seguimiento y cómo manejarlas

Pregunta de seguimiento 1: ¿Qué cambia si solo se requiere la distancia?

Elimina el arreglo previous y la reconstrucción del camino. La búsqueda, la demostración y los límites asintóticos siguen siendo los mismos, aunque el almacenamiento auxiliar de nodos se reduce en un arreglo de O(V). La salida temprana en la extracción actual del destino sigue siendo segura.

Pregunta de seguimiento 2: ¿Qué pasa si necesitamos las distancias más cortas desde cada origen?

Ejecutar Dijkstra desde cada nodo cuesta O(V(V + E) log E) con esta implementación. Para un grafo denso, Floyd-Warshall utiliza un tiempo de O(V^3) y un espacio de O(V^2) y también maneja aristas negativas cuando no hay ciclos negativos. El algoritmo de Johnson combina la reponderación con Dijkstra repetido para grafos dispersos con aristas negativas pero sin ciclos negativos. Elige según la densidad real del grafo y el volumen de consultas.

Pregunta de seguimiento 3: ¿Qué pasa si se permiten aristas negativas?

Usa Bellman-Ford para un grafo dirigido general. Relaja repetidamente todas las aristas, se ejecuta en O(VE) y una relajación exitosa adicional detecta un ciclo negativo alcanzable. El contraejemplo 0 -> 1 = 2, 0 -> 2 = 5, 2 -> 1 = -10 muestra el problema: Dijkstra con salida temprana asienta el destino 1 en 2, pero la verdadera ruta a través del nodo 2 cuesta -5.

Pregunta de seguimiento 4: ¿Qué pasa si el grafo es un DAG y algunas aristas son negativas?

Ordena topológicamente el DAG, luego relaja las aristas salientes una vez en orden topológico. Cada predecesor se procesa antes que su sucesor, por lo que los pesos negativos son seguros y el tiempo total es O(V + E). Esto supera a Bellman-Ford y a Dijkstra bajo el contrato acíclico más estricto.

Pregunta de seguimiento 5: ¿Qué pasa si cada peso es 0 o 1?

Usa 0-1 BFS con un deque. Inserta una relajación de peso cero al frente y una relajación de peso uno al final. El deque preserva el orden de distancias no decreciente, lo que da un tiempo de O(V + E) sin necesidad de un heap.

Pregunta de seguimiento 6: ¿Cómo cambiarían el diseño las actualizaciones frecuentes de aristas?

Para actualizaciones ocasionales, reconstruye la lista de adyacencia o modifica la arista afectada y vuelve a ejecutar Dijkstra; la solución simple es la más fácil de verificar. Las actualizaciones frecuentes con requisitos estrictos de latencia exigen técnicas dinámicas de caminos más cortos o árboles de origen en caché con invalidación, cuyo valor depende de la proporción entre actualizaciones y consultas y de la estructura del grafo. No afirmes que un cambio de arista local solo afecta a sus dos extremos.

Pregunta de seguimiento 7: ¿Cómo devolverías el camino más corto lexicográficamente más pequeño?

La comparación estricta de distancias por sí sola no es suficiente porque conserva deliberadamente el primer camino de igual costo. Define primero el contrato de ordenamiento. Un enfoque calcula las distancias más cortas, restringe las transiciones candidatas a aristas consistentes con esas distancias y luego selecciona el siguiente nodo válido más pequeño mientras asegura que el destino siga siendo alcanzable. Los ciclos de peso cero requieren un manejo consciente de ciclos. Comparar tuplas completas de caminos dentro de cada entrada del heap es más simple para entradas pequeñas, pero puede agregar un costo sustancial de copia y comparación.