Algoritmo de Dijkstra: el camino más corto en Python

Problema

Menos calles no es lo más rápido

Un mensajero sale del almacén hacia un cliente. La app tiene que darle la ruta más rápida. Cada calle tiene un tiempo en minutos: el bulevar es ancho pero está atascado, y las callejuelas son rápidas.

La ciudad es un grafo, y las calles son sus aristas en las dos direcciones (mira cómo se representa un grafo):

def add_street(city, a, b, minutes):
    city.setdefault(a, []).append((b, minutes))
    city.setdefault(b, []).append((a, minutes))

city = {}
add_street(city, "Almacén", "Puente", 2)
add_street(city, "Almacén", "Plaza", 5)
add_street(city, "Almacén", "Mercado", 15)
add_street(city, "Puente", "Plaza", 1)
add_street(city, "Puente", "Estación", 8)
add_street(city, "Plaza", "Estación", 3)
add_street(city, "Plaza", "Mercado", 9)
add_street(city, "Estación", "Cliente", 3)
add_street(city, "Mercado", "Cliente", 2)

La primera idea es BFS de la lección anterior: encuentra el camino más corto. Pero BFS cuenta calles, no minutos:

def fewest_streets(city, start):
    prev = {}
    seen = {start}
    queue = deque([start])
    while queue:
        place = queue.popleft()
        for to, _ in city[place]:
            if to not in seen:
                seen.add(to)
                prev[to] = place
                queue.append(to)
    return prev

city = {}
add_street(city, "Almacén", "Puente", 2)
add_street(city, "Almacén", "Plaza", 5)
add_street(city, "Almacén", "Mercado", 15)
add_street(city, "Puente", "Plaza", 1)
add_street(city, "Puente", "Estación", 8)
add_street(city, "Plaza", "Estación", 3)
add_street(city, "Plaza", "Mercado", 9)
add_street(city, "Estación", "Cliente", 3)
add_street(city, "Mercado", "Cliente", 2)
r = route(fewest_streets(city, "Almacén"), "Cliente")
print(f"Menos calles: {' → '.join(r)} ({len(r) - 1} calles, {minutes(city, r)} min)")

Menos calles: Almacén → Mercado → Cliente (2 calles, 17 min)

Dos calles, pero 17 minutos: 15 por el bulevar hasta el mercado y 2 hasta el cliente. Por el puente, la plaza y la estación son cuatro calles y solo 9 minutos. BFS ni siquiera mira los minutos.

La idea

Primero el lugar más cercano

BFS avanza por número de calles: primero todo lo que está a una calle, luego a dos. Aquí tienes que avanzar por minutos: primero el lugar al que llegas más rápido, luego el siguiente.

Eso es el algoritmo de Dijkstra (Edsger Dijkstra, 1956). Para cada lugar guarda el mejor tiempo hasta ahora, dist, y una cola de entradas «minutos, lugar».

Al principio dist es 0 para el almacén, y cualquier otro lugar está sin alcanzar (∞).
Toma de la cola la entrada con menos minutos. Es una cola de prioridad: saca la menor en O(log n).
Para cada calle de ese lugar, prueba: ¿llega al vecino más rápido que antes? Si es así, anota el nuevo tiempo, recuerda de dónde viniste (prev) y mete una entrada nueva en la cola. Este probar se llama relajación (relaxation).
Repite hasta que la cola quede vacía.

¿Por qué el lugar que sale de la cola ya tiene su tiempo definitivo? Todas las demás entradas tienen al menos tantos minutos, y cada calle suma minutos. Ningún camino que pase por ellas puede llegar antes.

Míralo

Dijkstra por dentro

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # obsoleta
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

heapq compara tuplas de izquierda a derecha: (minutes, place) sale por minutos. Un lugar que falta en dist aún no se ha alcanzado: eso es ∞.

prev guarda la ruta al revés: para cada lugar, de dónde vino el camino más rápido. Empiezas por el cliente, sigues prev hasta el almacén y le das la vuelta:

def route(prev, end):
    places = []
    at = end
    while at is not None:
        places.append(at)
        at = prev.get(at)
    return places[::-1]

dist, prev = dijkstra(city, "Almacén")
r = route(prev, "Cliente")
print(f"Más rápido: {' → '.join(r)} ({len(r) - 1} calles, {minutes(city, r)} min)")

Más rápido: Almacén → Puente → Plaza → Estación → Cliente (4 calles, 9 min)

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # obsoleta
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

Paso a paso, en palabras

El mensajero sale de Almacén: 0 minutos. Todos los demás lugares están en ∞, nada ha llegado todavía a ellos. La cola tiene una sola entrada: 0 Almacén.
Se toma la entrada más pequeña, 0 Almacén. Cada calle desde ahí da un tiempo: Puente 2, Plaza 5, Mercado 15. Todos son mejores que ∞: se anotan y entran en la cola.
Sigue 2 Puente. Pasando por ahí, Plaza cuesta 2 + 1 = 3, mejor que 5: cambian el tiempo y prev, y entra 3 Plaza. La entrada 5 Plaza se queda en la cola, ya está obsoleta. Estación recibe 10.
3 Plaza: definitivo, nada en la cola puede hacerlo más rápido. Pasando por ahí, Estación baja de 10 a 6 y Mercado de 15 a 12.
Arriba está 5 Plaza, pero Plaza ya tiene 3. La entrada está obsoleta: se salta. Es el borrado perezoso: en vez de buscar la entrada vieja en la cola, la tiras cuando sale.
6 Estación: definitivo. Cliente recibe 6 + 3 = 9. Volver a Puente con 14 y a Plaza con 9 no mejora nada.
9 Cliente: definitivo, 9 minutos. Pasando por Cliente, Mercado baja de 12 a 11. La frontera crece por tiempo, no por número de calles.
El resto: 10 Estación está obsoleta, 11 Mercado es definitiva y no mejora nada, 12 y 15 Mercado están obsoletas. La cola queda vacía.
prev da la ruta al revés: Cliente ← Estación ← Plaza ← Puente ← Almacén. Al darle la vuelta: Almacén → Puente → Plaza → Estación → Cliente, 9 minutos, cuatro calles. La ruta de dos calles por Mercado tarda 17.

Los lugares se vuelven definitivos en el orden de su tiempo: Almacén 0, Puente 2, Plaza 3, Estación 6, Cliente 9, Mercado 11. El mercado, a una calle del almacén, es el último.

Pruébalo

Predice la salida

¿Cuántos minutos hasta el mercado da Dijkstra?

city = {}
add_street(city, "Almacén", "Puente", 2)
add_street(city, "Almacén", "Plaza", 5)
add_street(city, "Almacén", "Mercado", 15)
add_street(city, "Puente", "Plaza", 1)
add_street(city, "Puente", "Estación", 8)
add_street(city, "Plaza", "Estación", 3)
add_street(city, "Plaza", "Mercado", 9)
add_street(city, "Estación", "Cliente", 3)
add_street(city, "Mercado", "Cliente", 2)
dist, prev = dijkstra(city, "Almacén")
print(dist["Mercado"])

Respuesta

La idea

Entradas obsoletas

Cuando la plaza recibe 3 minutos en vez de 5, la entrada «5 Plaza» ya está en la cola. ¿Por qué no cambiarla en su sitio?

Las colas integradas no pueden: heapq de Python son solo funciones sobre una lista, sin «cambiar prioridad». Así que el mejor tiempo entra como una entrada nueva. La vieja se queda, y cuando sale, la comprobación la tira: su tiempo es mayor que el de dist. Esto es el borrado perezoso (lazy deletion).

La cola puede tener más entradas que lugares, como máximo una por calle. El precio es un poco de memoria y algunas salidas vacías.

minutes, place = heapq.heappop(queue)
if :
    continue  # obsoleta

Pruébalo

Encuentra el error

Un compañero decidió que el primer tiempo encontrado es también el mejor, como en BFS:

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # obsoleta
        for to, length in city[place]:
            t = minutes + length
            if to not in dist:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

dist, prev = dijkstra(city, "Almacén")
r = route(prev, "Cliente")
print(f"Más rápido: {' → '.join(r)} ({len(r) - 1} calles, {minutes(city, r)} min)")

Más rápido: Almacén → Puente → Estación → Cliente (3 calles, 13 min)

13 minutos en vez de 9. ¿En qué línea está el error?

Elige la línea con el error.

La idea

Cuánto cuesta

Cada calle se prueba dos veces (una desde cada extremo) y puede añadir una entrada. Cada entrada entra y sale una vez, a O(log V). En total O((V + E) log V) para V lugares y E calles.

Sin la cola, el lugar más cercano se busca con un bucle sobre todos los lugares que aún no son definitivos. Así se escribió originalmente el algoritmo:

def dijkstra_scan(city, start):
    dist = {place: math.inf for place in city}
    dist[start] = 0
    done = set()
    while len(done) < len(city):
        best = None
        for place in city:
            if place not in done and (best is None or dist[place] < dist[best]):
                best = place
        if dist[best] == math.inf:
            break
        done.add(best)
        for to, length in city[best]:
            t = dist[best] + length
            if t < dist[to]:
                dist[to] = t
    return dist

city = {}
add_street(city, "Almacén", "Puente", 2)
add_street(city, "Almacén", "Plaza", 5)
add_street(city, "Almacén", "Mercado", 15)
add_street(city, "Puente", "Plaza", 1)
add_street(city, "Puente", "Estación", 8)
add_street(city, "Plaza", "Estación", 3)
add_street(city, "Plaza", "Mercado", 9)
add_street(city, "Estación", "Cliente", 3)
add_street(city, "Mercado", "Cliente", 2)
dist = dijkstra_scan(city, "Almacén")
print(", ".join(f"{p} {dist[p]}" for p in ["Almacén", "Puente", "Plaza", "Estación", "Mercado", "Cliente"]))

Almacén 0, Puente 2, Plaza 3, Estación 6, Mercado 11, Cliente 9

La respuesta es la misma. Pero el bucle tiene V pasos, y se hace V veces: O(V²).

Ejecuta las dos versiones en un barrio donde los cruces forman una cuadrícula y cada uno está unido a su vecino de la derecha y al de abajo. Cada calle dura de 1 a 9 minutos. Se cuenta cada comparación de dos tiempos: al buscar el lugar más cercano, dentro de la cola y al probar una calle.

Sin cola: un bucle para el más cercano O(n²)
Con una cola de prioridad O(n log n)

Algoritmo	n = 100	n = 1000	n = 10.000	n = 100.000
Sin cola: un bucle para el más cercano	5410	504.372	≈ 50.437.200	≈ 5.043.720.000
Con una cola de prioridad	1269	17.121	213.675	2.554.618

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

def dijkstra(city, start):
    dist = {start: 0}
    prev = {}
    queue = [(0, start)]
    while queue:
        minutes, place = heapq.heappop(queue)
        if minutes > dist[place]:
            continue  # obsoleta
        for to, length in city[place]:
            t = minutes + length
            if to not in dist or t < dist[to]:
                dist[to] = t
                prev[to] = place
                heapq.heappush(queue, (t, to))
    return dist, prev

Con 1000 cruces, la versión sin cola hace 504 372 comparaciones, la que tiene cola 17 121. Con 100 000 cruces, el tamaño de una ciudad grande, la cola hace 2 554 618. Sin ella serían unos 5 mil millones: Bench no las ejecuta, las estima a partir de la curva.

Más precisamente, para curiosos

¿Cuándo es mejor O(V²)? Cuando el grafo es denso: cada lugar está unido a casi todos los demás, y E es más o menos V². Entonces la cola hace O(V² log V) y el bucle O(V²). En una red de carreteras cada cruce tiene 3 o 4 calles, el grafo es ralo y gana la cola.

Los pesos negativos rompen Dijkstra. Si una calle cuesta −5 (digamos, una bonificación de entrega en el camino), un lugar que ya es definitivo puede acercarse después por ella, y el algoritmo ya no lo mira. Para esos grafos existe Bellman-Ford: prueba cada calle V − 1 veces, O(V · E), y avisa si hay un ciclo que reduce el tiempo sin fin.

En Python ∞ es math.inf: math.inf + 5 sigue siendo math.inf, y los enteros no desbordan. En Java y C# ∞ suele ser el int más grande, y sumarle minutos da un número negativo.

La navegación de tu teléfono no ejecuta Dijkstra sobre todo un continente. Usa A*: un Dijkstra que suma a los minutos de la cola una estimación de cuánto falta en línea recta, y por eso avanza hacia la meta en vez de expandirse en todas las direcciones. OSPF, el protocolo con el que los routers de una red encuentran el camino de los paquetes, ejecuta Dijkstra de verdad.

Ejercicio

Una calle cerrada

Resuelve la tarea en tu editor.

Obras. La calle entre el puente y la plaza está cerrada. Quítala de la ciudad (en las dos direcciones) y muestra la ruta más rápida y los minutos hasta la estación, el cliente y el mercado:

Estación: Almacén → Plaza → Estación (8 min)
Cliente: Almacén → Plaza → Estación → Cliente (11 min)
Mercado: Almacén → Plaza → Estación → Cliente → Mercado (13 min)

El mercado sigue siendo más rápido pasando por el cliente: 13 minutos contra 14 por la plaza y 15 por el bulevar.

Más tareas

Para a tiempo. Si solo te interesa el cliente, para en cuanto salga de la cola. ¿Cuántas entradas quedan sin tomar?
Cuenta las salidas. Cuenta cuántas entradas salieron de la cola y cuántas de ellas estaban obsoletas.
Dos mensajeros. Dos almacenes, un cliente: ¿qué mensajero llega primero? Pista: mete los dos almacenes en la cola con 0 minutos.

Test

Ponte a prueba

1. ¿Por qué BFS no encuentra la ruta más rápida cuando las calles tienen minutos?BFS solo funciona con árbolesBFS cuenta calles: encuentra el camino con menos calles, y ese puede ser más lentoBFS no llega a todos los lugares

2. Un lugar sale de la cola con los menos minutos de todas las entradas. ¿Por qué su tiempo es definitivo?Porque nada apunta a élPorque la cola está ordenada por número de callesCualquier otro camino pasa por un lugar con al menos tantos minutos, y las calles no son negativas

3. En la cola hay 5 Plaza, y Plaza ya tiene 3 minutos. ¿Qué hace el algoritmo cuando sale 5 Plaza?La salta: la entrada está obsoletaCambia el tiempo de Plaza a 5Se detiene: se encontró un ciclo

4. ¿Cuánto cuesta Dijkstra con un heap binario para V lugares y E calles?O(V + E)O((V + E) log V)O(V²)

Dijkstra

Cookies