Grafos y caminos mínimos: Dijkstra

La idea

Un grafo es un conjunto de vértices unidos por aristas, y cuando las aristas llevan un número asociado (distancia, tiempo, coste, latencia) se llama ponderado. El problema del camino mínimo pide la ruta de peso total menor entre dos vértices. El algoritmo de Dijkstra (1959) lo resuelve con una estrategia voraz: mantiene una estimación d[v] de la distancia desde el origen, inicializada en 0 para el origen e ∞ para el resto, y en cada iteración cierra el vértice abierto con d[v] más pequeño, dando su valor por definitivo.

Al cerrar un vértice u se relajan sus aristas: para cada vecino v, si d[u] + w(u, v) < d[v] se mejora la estimación y se apunta que a v se llega mejor viniendo de u. Guardando esos predecesores se reconstruye el camino al final recorriéndolos hacia atrás. La corrección depende crucialmente de que los pesos sean no negativos: solo así el mínimo entre los abiertos no puede mejorarse después, porque cualquier ruta alternativa tendría que pasar por un vértice ya más lejano. Con aristas negativas hay que usar Bellman-Ford, que además detecta ciclos de peso negativo.

El coste depende de la estructura elegida para encontrar el mínimo. Con búsqueda lineal sobre un arreglo es O(V²), razonable en grafos densos; con una cola de prioridad binaria es O((V + E) log V), lo adecuado para redes dispersas como las viales. Variantes muy usadas son A*, que acelera la búsqueda sumando una heurística admisible de distancia al destino, y Dijkstra bidireccional, que explora desde los dos extremos a la vez.

Fórmulas clave

• Inicializaciónd[origen] = 0, d[v] = ∞ para v ≠ origen
• Relajación de aristasi d[u] + w(u, v) < d[v] → d[v] = d[u] + w(u, v), prev[v] = u
• Selección vorazcerrar u = argmin { d[v] : v abierto }
• Coste con arreglo / con montículoO(V²) / O((V + E) log V)
• Condición de validezw(u, v) ≥ 0 para toda arista
• A* (heurística admisible)f(v) = d[v] + h(v), con h(v) ≤ distancia real a destino

Dónde se aplica

Los navegadores y las aplicaciones de mapas calculan rutas con descendientes de Dijkstra: A*, jerarquías de contracción y etiquetado de nodos, sobre grafos con decenas de millones de aristas y pesos que cambian con el tráfico. En redes de datos, el protocolo de enrutamiento OSPF ejecuta Dijkstra en cada router para construir su tabla de reenvío. En logística se usa como subrutina del reparto de mercancías y del diseño de rutas de transporte público, y en biología computacional para encontrar trayectos de mínimo coste en redes metabólicas o de interacción de proteínas.

Con programación (Python)

import heapq

grafo = {
    "A": {"B": 4, "C": 2},
    "B": {"C": 5, "D": 10},
    "C": {"E": 3},
    "D": {"F": 11},
    "E": {"D": 4},
    "F": {},
}

def dijkstra(g, origen):
    dist = {v: float("inf") for v in g}
    prev = {v: None for v in g}
    dist[origen] = 0
    monticulo, cerrados = [(0, origen)], set()
    while monticulo:
        d, u = heapq.heappop(monticulo)
        if u in cerrados:
            continue
        cerrados.add(u)
        for v, w in g[u].items():
            if d + w < dist[v]:
                dist[v], prev[v] = d + w, u
                heapq.heappush(monticulo, (dist[v], v))
    return dist, prev

def camino(prev, destino):
    ruta = []
    while destino is not None:
        ruta.append(destino)
        destino = prev[destino]
    return list(reversed(ruta))

dist, prev = dijkstra(grafo, "A")
for v in sorted(dist):
    print(f"A -> {v}: distancia {dist[v]:>4}  camino {' - '.join(camino(prev, v))}")

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Complejidad y notación O grande · El problema de la mochila · Cadenas de Markov