Algoritmo de Dijkstra: cómo encontrar el camino más corto en un grafo

El algoritmo de Dijkstra, desarrollado por el informático holandés Edsger Dijkstra en 1956, es uno de los algoritmos más importantes de la ciencia de la computación. Resuelve el problema del camino más corto desde un nodo origen hasta todos los demás nodos en un grafo con pesos no negativos.

Aplicaciones reales

• GPS y navegación: Google Maps usa variantes de Dijkstra para calcular rutas.
• Redes informáticas: los routers usan protocolos basados en Dijkstra (OSPF).
• Videojuegos: para calcular caminos de NPCs (junto con A*).
• Redes sociales: para encontrar conexiones entre personas.

Cómo funciona paso a paso

1. Asigna distancia 0 al nodo origen y ∞ a todos los demás.
2. Marca todos los nodos como no visitados.
3. Elige el nodo no visitado con la distancia más pequeña.
4. Para cada vecino, calcula si la ruta a través del nodo actual es más corta que la conocida.
5. Marca el nodo actual como visitado y repite desde el paso 3.

Implementación en Python

import heapq

def dijkstra(grafo, inicio):
    distancias = {nodo: float('inf') for nodo in grafo}
    distancias[inicio] = 0
    cola = [(0, inicio)]  # (distancia, nodo)
    
    while cola:
        dist_actual, nodo_actual = heapq.heappop(cola)
        
        if dist_actual > distancias[nodo_actual]:
            continue
            
        for vecino, peso in grafo[nodo_actual].items():
            distancia = dist_actual + peso
            if distancia < distancias[vecino]:
                distancias[vecino] = distancia
                heapq.heappush(cola, (distancia, vecino))
    
    return distancias

# Ejemplo: red de ciudades
grafo = {
    'Madrid':   {'Barcelona': 621, 'Valencia': 352, 'Sevilla': 534},
    'Barcelona': {'Madrid': 621, 'Valencia': 349},
    'Valencia': {'Madrid': 352, 'Barcelona': 349, 'Sevilla': 654},
    'Sevilla':  {'Madrid': 534, 'Valencia': 654}
}

print(dijkstra(grafo, 'Madrid'))
# {'Madrid': 0, 'Barcelona': 621, 'Valencia': 352, 'Sevilla': 534}

Complejidad

Con una cola de prioridad (heap): O((V + E) log V), donde V es el número de vértices y E el número de aristas. Muy eficiente para grafos dispersos.

Limitación importante

Dijkstra no funciona con pesos negativos. Para ese caso, usa el algoritmo de Bellman-Ford.