El Algoritmo de Dijkstra Explicado, Paso a Paso

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

¿Qué Es el Algoritmo de Dijkstra?

El algoritmo de Dijkstra, publicado por Edsger W. Dijkstra en 1959, encuentra el camino más corto desde un único origen hasta todos los demás nodos de un grafo ponderado. Funciona tanto en grafos dirigidos como no dirigidos, con una condición firme: todo peso de arista debe ser no negativo.

Piensa en el grafo como una red de carreteras. Los nodos son cruces, las aristas son carreteras y cada peso es el tiempo o la distancia para recorrer esa carretera. El algoritmo de Dijkstra responde a la pregunta que hace toda app de navegación: ¿cuál es la ruta más rápida desde donde estoy hasta todo lo demás? Es una pieza de la familia más amplia que se cubre en algoritmos de caminos más cortos, y un elemento fijo de la hoja de ruta de teoría de grafos.

La Idea Central

El algoritmo de Dijkstra es voraz. Mantiene una distancia más corta tentativa a cada nodo y repite un movimiento sencillo:

Visita siempre el nodo no visitado con la menor distancia conocida y úsalo para mejorar a sus vecinos.

La idea que lo hace correcto: como todos los pesos son no negativos, una vez que eliges el nodo no visitado más cercano, ningún camino futuro puede alcanzarlo más barato. Así que en el momento en que se elige un nodo, su distancia es definitiva. Esa única garantía es todo el algoritmo.

En concreto, el algoritmo mantiene:

• Una distancia a cada nodo, todas empezando en infinito salvo el origen, que es 0.
• Una cola de prioridad (min-heap) que siempre devuelve el nodo no visitado más cercano.
• Un conjunto de nodos definitivos cuya distancia más corta ya está resuelta.

Mejorar a un vecino se llama relajación: si el camino a través del nodo actual es más corto que la distancia registrada del vecino, la bajas.

Cómo Funciona, Paso a Paso

Ejecutemos Dijkstra desde el nodo A en este grafo ponderado. Las aristas azules formarán el árbol final de caminos más cortos, y el número junto a cada nodo es su distancia más corta final desde A.

Aquí está la traza. En cada paso fijamos como definitivo el nodo no visitado más cercano (en negrita) y relajamos a sus vecinos. ∞ significa "aún no alcanzado".

Fíjate en el paso tres: visitar C bajó B de 4 a 3, porque la ruta A → C → B (2 + 1) supera a la arista directa A → B (4). Eso es la relajación haciendo su trabajo. Ver esto desplegarse en un grafo en vivo hace que el patrón sea instantáneo, lo que puedes hacer en el visualizador de algoritmos.

Implementación en Python

La versión limpia y lista para entrevistas usa heapq de Python como cola de prioridad. El grafo es una lista de adyacencia que asigna a cada nodo una lista de pares (vecino, peso).

import heapq

def dijkstra(graph, start):
    # Cada nodo empieza infinitamente lejos, salvo el origen.
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distancia hasta ahora, nodo)

    while pq:
        dist, node = heapq.heappop(pq)

        # Una entrada obsoleta y más larga de un nodo ya resuelto: se omite.
        if dist > distances[node]:
            continue

        for neighbour, weight in graph[node]:
            new_dist = dist + weight
            # Relajación: se encontró una forma más barata de llegar al vecino.
            if new_dist < distances[neighbour]:
                distances[neighbour] = new_dist
                heapq.heappush(pq, (new_dist, neighbour))

    return distances

Dos detalles importan. Primero, insertamos una entrada nueva en lugar de actualizar el montículo en su sitio, y luego omitimos las entradas obsoletas con la comprobación dist > distances[node]. Este "borrado perezoso" mantiene el código simple y es práctica estándar. Segundo, el algoritmo calcula de forma natural las distancias a todos los nodos; para detenerte antes en un único destino, retorna en cuanto lo extraigas.

Complejidad en Tiempo y Espacio

El costo depende de la cola de prioridad. Cada arista puede provocar como mucho una inserción, y cada inserción o extracción en un montículo binario cuesta O(log V).

El espacio es O(V) para la tabla de distancias más la cola. Para el razonamiento detrás de estas cotas y cómo se comparan entre todos los algoritmos de grafos, consulta la guía de complejidad de algoritmos de grafos y la chuleta de una página.

Cuándo Falla Dijkstra: Pesos Negativos

La garantía voraz descansa por completo en los pesos no negativos. Añade una arista negativa y todo puede romperse.

Supón que el algoritmo fija un nodo como definitivo porque parece el más cercano, distancia 5. Después descubre una ruta que parece más larga, que pasa por una arista -4 y en realidad alcanza ese nodo en 3. Demasiado tarde: Dijkstra ya declaró 5 como definitivo y siguió adelante. La respuesta es incorrecta.

Regla para recordar: pesos no negativos, usa Dijkstra. Cualquier peso negativo, usa Bellman-Ford, que relaja cada arista repetidamente y además puede detectar ciclos negativos.

Dijkstra frente a Otros Algoritmos

Dijkstra es una herramienta entre varias. Elegir la correcta se reduce al grafo.

El pariente más cercano es la búsqueda A*, que es Dijkstra más una heurística que dirige la búsqueda hacia un único objetivo. Y Dijkstra en sí mismo es en realidad la búsqueda en anchura mejorada de una cola simple a una cola de prioridad.

Aplicaciones en el Mundo Real

• Navegación y mapas: la ruta más corta o más rápida entre dos lugares, el uso clásico.
• Enrutamiento de redes: los protocolos de estado de enlace como OSPF usan Dijkstra para calcular las tablas de reenvío.
• Videojuegos y robótica: costos de movimiento por un mapa, a menudo con A* construido encima.
• Operaciones y logística: caminos de mínimo costo en redes de suministro, telecomunicaciones y transporte, un pilar de la investigación de operaciones.