Algoritmos Avanzados en Python

Resolviendo problemas con grafos

La ciudad de PyEnvíos tiene 12 zonas unidas por 20 calles, cada una con su tiempo en minutos. Con ese mapa se responden preguntas muy distintas: ¿se puede llegar a todas las zonas?, ¿cuál es la ruta con menos calles?, ¿y la más rápida?, ¿cuánto tarda la camioneta entre cualquier par de zonas? El notebook grafos-pyenvios las resuelve con la biblioteca estándar y verifica cada resultado con networkx; esta lección es su guía.

1. Construir el grafo

La lista CIUDAD trae tuplas (zona, zona, minutos). Como las calles son de doble sentido, el grafo es no dirigido: cada calle se agrega en las dos direcciones. grafo_ciudad() devuelve una lista de adyacencia, un diccionario {zona: [(vecina, minutos), ...]}. La alternativa es una matriz de adyacencia de 12 × 12: 144 celdas, de las que solo 40 tienen valor (20 calles × 2 sentidos). En grafos dispersos como un mapa urbano, la lista ocupa memoria proporcional a las calles y recorre los vecinos de una zona sin revisar las 12 columnas.

2. BFS, DFS y componentes conexas

BFS explora por capas con una deque: primero las zonas a una calle, luego a dos. Por eso encuentra la ruta con menos calles: de Almacén a Estadio, Almacén–Industrial–Puerto–Estadio, 3 calles y 30 minutos. DFS se hunde por un camino antes de retroceder; no da rutas cortas, pero sirve para recorrer todo y para detectar ciclos. Un recorrido también responde si el mapa está conectado: se lanza desde cada zona no visitada y cada lanzamiento descubre una componente conexa.

from collections import deque

G = grafo_ciudad()

def componentes(g):
    vistos, comps = set(), []
    for s in g:
        if s in vistos:
            continue
        vistos.add(s)
        cola, comp = deque([s]), []
        while cola:
            u = cola.popleft()
            comp.append(u)
            for v, _ in g[u]:
                if v not in vistos:
                    vistos.add(v)
                    cola.append(v)
        comps.append(comp)
    return comps

print(len(G), sum(len(v) for v in G.values()) // 2, len(componentes(G)))   # 12 20 1

La ciudad tiene una sola componente: la camioneta puede llegar a todas las zonas desde el Almacén. Si una calle se cierra por obra, basta quitarla y volver a contar.

3. Dijkstra con reconstrucción de la ruta

Para minimizar minutos, no calles, se usa Dijkstra con heapq. El diccionario prev guarda de qué zona se llegó a cada una; recorrerlo hacia atrás desde el destino reconstruye la ruta:

import heapq, math

def dijkstra(g, s):
    dist, prev, pq = {s: 0}, {s: None}, [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in g[u]:
            if d + w < dist.get(v, math.inf):
                dist[v], prev[v] = d + w, u
                heapq.heappush(pq, (d + w, v))
    return dist, prev

dist, prev = dijkstra(G, "Almacén")
ruta, z = [], "Estadio"
while z is not None:
    ruta.append(z)
    z = prev[z]
print(ruta[::-1], dist["Estadio"])   # 5 calles, 25 min

La ruta más rápida es Almacén–Centro–Mercado–Parque–Hospital–Estadio: 5 calles y 25 minutos, contra las 3 calles y 30 minutos de BFS. Menos calles no significa menos tiempo. El notebook compara el resultado con nx.dijkstra_path, que da la misma ruta.

4. Matriz de distancias entre todos los puntos

Ejecutar Dijkstra desde cada una de las 12 zonas produce una matriz de 12 × 12 con el tiempo mínimo entre cualquier par. Es la entrada del proyecto final: el planificador de rutas ya no piensa en calles, solo en esa tabla. La zona más alejada del Almacén es Aeropuerto, a 28 minutos, y el par más distante de toda la ciudad es Puerto–Aeropuerto, a 32 minutos.

5. Bellman-Ford y pesos negativos

Dijkstra supone que ningún peso es negativo: cuando cierra una zona, da su distancia por definitiva. En un grafo pequeño con una arista de −3 (A→B 1, A→C 3, C→B −3, B→D 1), la versión de libro dice que A→D cuesta 2, y el valor correcto es 1. Bellman-Ford relaja todas las aristas $|V| - 1$ veces, con costo $O(|V| \cdot |E|)$, y acepta pesos negativos; una pasada extra que todavía mejore algo revela un ciclo negativo. En la ciudad, sin pesos negativos, ambos coinciden.

6. Extra: orden topológico

Un grafo dirigido y sin ciclos modela dependencias. Las tareas del almacén tienen un orden obligado, y el algoritmo de Kahn lo encuentra sacando siempre una tarea sin pendientes:

deps = {"recibir": ["pesar", "etiquetar"], "pesar": ["asignar ruta"],
        "etiquetar": ["cargar"], "asignar ruta": ["cargar"], "cargar": ["salir"], "salir": []}
entrantes = {t: 0 for t in deps}
for t in deps:
    for s in deps[t]:
        entrantes[s] += 1
cola, orden = deque(t for t in deps if entrantes[t] == 0), []
while cola:
    t = cola.popleft()
    orden.append(t)
    for s in deps[t]:
        entrantes[s] -= 1
        if entrantes[s] == 0:
            cola.append(s)
print(orden)   # recibir, pesar, etiquetar, asignar ruta, cargar, salir

Si al final orden tiene menos tareas que deps, hay un ciclo y no existe un orden válido.

Trampas comunes

• Agregar la calle en un solo sentido en un grafo no dirigido: la mitad de las rutas desaparecen.
• Usar BFS para minutos: BFS minimiza aristas, no pesos.
• Marcar como visitado al sacar de la cola en BFS: una zona entra varias veces; se marca al encolar.
• Dijkstra con pesos negativos: no avisa, solo se equivoca.

Cierre

Al terminar el notebook, dibuja el grafo con networkx y resalta la ruta de Dijkstra. Después guarda la función que construye la matriz de distancias: es la primera pieza del proyecto final.