Dejamos las listas y volvemos a la red de paradas que modelamos como grafo en 03-04 — esta vez con la pregunta estrella de cualquier app de movilidad: ¿cuántos minutos se tarda, como mínimo, de una parada a cada una de las demás? El algoritmo que la responde lo anunciamos en 03-02 con nombre y apellido: Dijkstra, "el greedy que sí es óptimo". Después de ver estrategias voraces que fallaban (cambio_greedy, recorrido_supervisor), aquí estudiaremos la que triunfa: por qué su elección voraz — consolidar siempre la parada más cercana pendiente — es irrevocablemente correcta cuando los pesos no son negativos, cómo implementarla eficientemente con una cola de prioridad (heapq), y cómo reconstruir el camino además de su coste. Lo trazaremos completo desde Plaza Mayor y cerraremos con su complejidad y su única kryptonita: los pesos negativos.

1. La red de RutaBus como grafo ponderado
2. El problema: caminos más cortos desde un origen
3. La idea greedy y por qué funciona
4. Cuadro previo: qué es un heap / cola de prioridad
5. Implementación con heapq
6. Traza completa desde Plaza Mayor
7. Reconstruir el camino: predecesores
8. Complejidad y la limitación de los pesos negativos

En 03-04 la red era un diccionario de adyacencia que solo decía quién conecta con quién. Para hablar de tiempos necesitamos añadir pesos: los minutos de trayecto de cada tramo. Basta cambiar las listas de vecinas por diccionarios vecina → minutos:

Vocabulario mínimo: las paradas son los vértices (V = 5), los tramos son las aristas (E = 6) y los minutos, sus pesos. Nuestro grafo es no dirigido — cada tramo aparece en ambos sentidos con el mismo peso —; si la L3 tuviera un tramo de sentido único, bastaría con anotarlo solo en una dirección, y todo lo que sigue funcionaría igual.

El coste de un camino es la suma de los pesos de sus tramos. De Plaza Mayor a Hospital Central hay varios: por Estación Norte (4 + 5 = 9), por Parque del Río directo (2 + 8 = 10), por Parque del Río y Universidad (2 + 3 + 6 = 11). El problema del camino más corto desde un origen (single-source shortest paths) pide, para un origen dado, la distancia mínima a todas las demás paradas — exactamente lo que RutaBus necesita para responder "¿cuánto tardo desde aquí?" a un usuario plantado en Plaza Mayor.

¿Por qué no vale nada de lo que ya tenemos? El backtracking de 03-04 (rutas_inspeccion) enumeraría todos los caminos posibles — exponencial. Y ojo con la trampa de "el camino con menos paradas": el tramo directo PR→HC (8 min) pierde contra el rodeo PR→UNI→HC (9 min... no, 3+6=9, aquí gana el directo — pero PM→HC por EN con dos tramos gana al directo por PR con dos tramos). Menos tramos no implica menos minutos: hay que contar pesos, no saltos. (Contar saltos es lo que haría una búsqueda en anchura, BFS — una línea de mención y seguimos, porque con pesos no basta.)

Dijkstra mantiene para cada parada una distancia provisional (la mejor encontrada hasta el momento, ∞ si ninguna) y aplica este bucle voraz, puro 03-02:

De entre las paradas aún no consolidadas, toma la de menor distancia provisional, declála definitiva, y relaja sus aristas: para cada vecina, comprueba si pasar por la recién consolidada mejora su provisional.

La "relajación" es la operación elemental: si dist[parada] + minutos(parada, vecina) < dist[vecina], hemos encontrado un atajo y actualizamos.

¿Por qué esta elección voraz nunca se equivoca? El argumento — primo del argumento de intercambio de 03-02 — se apoya en una única hipótesis: ningún peso es negativo. Sea p la parada no consolidada con menor provisional d. ¿Podría existir un camino a p más corto que d, aún no descubierto? Ese camino saldría de la zona consolidada en algún punto y atravesaría alguna otra parada no consolidada q antes de llegar a p. Pero solo llegar a q ya cuesta al menos su provisional, que es ≥ d (¡p era la mínima!), y desde q hasta p los tramos restantes suman ≥ 0 (aquí entra la hipótesis). Total: ≥ d. Ningún rodeo puede batir a d, así que consolidar p con d es seguro — para siempre. Es un greedy con la propiedad que a recorrido_supervisor le faltaba: cada decisión local viene con una garantía global demostrada.

Cola de prioridad y heap, en cuatro líneas. Una cola de prioridad es una estructura que permite insertar elementos con una prioridad y extraer siempre el de prioridad mínima. Su implementación estándar es el heap binario: un árbol casi completo guardado en una lista donde cada nodo es ≤ que sus hijos, de modo que el mínimo vive siempre en la raíz (posición 0). Insertar (heappush) y extraer el mínimo (heappop) cuestan O(log n) — el elemento "flota" o "se hunde" a lo largo de los ~log₂ n niveles del árbol, el mismo conteo de mitades de 04-01. En Python lo da hecho el módulo heapq, que opera sobre listas normales; con tuplas (prioridad, dato) compara primero la prioridad.

¿Para qué lo queremos? El paso voraz exige localizar "la parada pendiente con menor provisional" muchas veces. Buscarla con un recorrido lineal costaría O(V) cada vez; el heap la sirve en O(log V).

Tres decisiones de diseño que conviene entender:

• Entradas obsoletas. Cuando la provisional de una parada mejora, no editamos su entrada antigua en el heap (los heaps no soportan eso con gracia): añadimos otra con la distancia nueva. La nueva, al ser menor, saldrá antes; cuando más tarde aflore la vieja, el if parada in consolidadas: continue la desecha. Es la técnica de la eliminación perezosa: más simple y en la práctica igual de eficiente.
• dist empieza en infinito (float("inf")): "todavía no conozco ningún camino". El infinito de coma flotante compara correctamente con cualquier suma de minutos y evita tratar los "sin descubrir" como caso especial.
• previa apunta, para cada parada, desde dónde se la alcanzó por última vez con mejora — la miga de pan que en el apartado 7 nos devolverá el camino completo, no solo su coste.

Ejecutemos dijkstra(red, "Plaza Mayor"). Abreviamos: PM, EN, HC, PR, UNI. Cada fila es una vuelta del while que consolida una parada:

Resultado: desde Plaza Mayor se tarda 0 (PM), 4 (EN), 9 (HC), 2 (PR) y 5 (UNI) minutos como mínimo. La traza exhibe los dos comportamientos característicos:

• El orden de consolidación (PM, PR, EN, UNI, HC) es por distancia creciente — el frente voraz se expande como una onda desde el origen.
• El paso 3 muestra una relajación que corrige: HC había sido descubierto vía PR (10 min) pero la ruta por EN lo mejora a 9. La provisional era eso, provisional; solo al consolidarse (paso 5) se vuelve verdad definitiva. Y el paso 6 muestra la entrada obsoleta (10, HC) muriendo en silencio.

dist responde "cuánto"; el usuario quiere "por dónde". La respuesta está en previa, que tras la ejecución vale:

Es la misma jugada que la reconstrucción de la mochila en 03-03: durante el algoritmo no guardamos los caminos (serían muchos y largos), guardamos una miga por parada — quién la alcanzó por última vez con mejora — y al final recorremos las migas hacia atrás:

Nótese la elegancia estructural: los punteros previa forman un árbol de caminos mínimos con raíz en el origen — un solo diccionario codifica el mejor camino a todas las paradas a la vez.

Tiempo. Contemos con las herramientas de 02-01, siendo V las paradas y E los tramos:

• Cada parada se consolida una sola vez, y al consolidarse relaja sus aristas; cada arista se relaja por tanto O(1) veces por extremo → O(E) relajaciones en total.
• Cada relajación que mejora hace un heappush de O(log·tamaño del heap). El heap contiene a lo sumo O(E) entradas (por las obsoletas), y log E ≤ log V² = 2·log V — constante fuera (01-03) —, así que cada operación de heap es O(log V).
• Extracciones: O(V + E) heappop, también a O(log V).

Total: O((V + E) · log V). Para la red real de RutaBus — dispersa: cada parada conecta con 2-4 vecinas, E ≈ 2V — esto es casi lineal: con 10.000 paradas, del orden de 4·10⁵ operaciones de heap. La alternativa sin heap (buscar el mínimo con un barrido lineal) costaría O(V²) — 10⁸ —, que solo compensa en grafos muy densos.

Espacio: O(V + E) — los diccionarios dist/previa y el heap. Auxiliar lineal, sin sustos.

La kryptonita: pesos negativos. Toda la demostración del apartado 3 colgaba de "los tramos restantes suman ≥ 0". Si un peso puede ser negativo — imagina un tramo bonificado donde el bus recupera 4 minutos de horario — el argumento se derrumba, y con él el algoritmo:

Dijkstra desde A consolida B con distancia 3 (es la mínima provisional: 3 < 5) y la declara intocable. Pero el camino A→C→B cuesta 5 + (−4) = 1. La consolidación voraz — "nada puede mejorar al mínimo actual" — era mentira: un rodeo aparentemente caro escondía un descuento. Con minutos de trayecto esto no ocurre (el tiempo no retrocede), pero sí en cuanto los pesos modelan costes con reembolsos, diferencias o saldos. Para esos grafos hacen falta algoritmos que no consoliden tan alegremente — y uno de ellos, que además responde a todas-las-paradas-contra-todas de una tacada, es exactamente la próxima lección: Floyd-Warshall.

• Usarlo con pesos negativos: no avisa, no falla — devuelve distancias incorrectas con total seguridad en sí mismo. Si tus pesos pueden ser negativos, Dijkstra está descartado de entrada (apartado 8).
• Olvidar el descarte de obsoletas (if parada in consolidadas: continue): el algoritmo re-procesa paradas con distancias viejas; en grafos con muchos ciclos puede dar resultados correctos por casualidad pero disparar el coste, o corromper previa. Las entradas duplicadas en el heap son diseño, el descarte es su otra mitad.
• Poner la tupla del heap al revés ((parada, distancia)): heapq compara el primer campo — ordenarías alfabéticamente por nombre de parada, y el "greedy" consolidaría Estación Norte antes que Parque del Río sin mirar minutos. Prioridad SIEMPRE primero.
• Confundir "descubierta" con "consolidada": la provisional de una parada puede mejorar varias veces (HC: ∞ → 10 → 9) mientras no esté consolidada. Tratar la primera provisional como definitiva es reinventar el error de los pesos negativos sin necesitarlos.
• Consejo: para depurar, imprime en cada vuelta la parada consolidada y su distancia. Deben salir en orden no decreciente; si ves un retroceso, tienes pesos negativos o un bug — esa monotonía es la firma del algoritmo.

Añade la parada "Terminal Sur" conectada con "Universidad" (7 min) y con "Hospital Central" (1 min). Traza dijkstra(red, "Plaza Mayor") con la tabla del apartado 6: orden de consolidación, distancias finales y previa. ¿En qué paso mejora Terminal Sur su provisional?

RutaBus quiere el camino más corto entre dos paradas concretas (origen → destino), no a todas. Modifica dijkstra para que pueda parar antes: ¿en qué momento exacto es seguro devolver la respuesta para destino, y por qué? (La justificación es el corazón de la lección.)

Un becario propone arreglar los pesos negativos así: "sumo a todos los tramos una constante K suficientemente grande para que ninguno quede negativo, ejecuto Dijkstra y ya". Encuentra el fallo con este contraejemplo: A→B directo (peso 1) contra A→C→B (pesos −1 y 1), con K = 2. ¿Qué camino es realmente el más corto y cuál elige el Dijkstra "arreglado"?

Solución 1

Con TS conectado a UNI (7) y HC (1):

Terminal Sur mejora en el paso 5: descubierta vía Universidad (12), corregida vía Hospital Central (10). previa["Terminal Sur"] = "Hospital Central", y el camino es PM → EN → HC → TS (4+5+1 = 10). Fíjate: el vecino "caro" (HC a 9 min) resultó mejor puerta que el "barato" (UNI a 5) — por eso no se puede consolidar TS hasta que le llega el turno.

Solución 2

Se puede devolver dist[destino] en el momento en que destino se consolida (sale del heap y pasa el filtro de obsoletas):

Justificación: la consolidación es exactamente la garantía de que esa distancia ya no puede mejorar (argumento del apartado 3, válido porque los pesos son ≥ 0). Detenerse antes — por ejemplo, la primera vez que destino recibe una provisional — sería incorrecto: HC recibió 10 antes que 9 en nuestra traza. En el mejor caso (destino cercano) el ahorro es enorme; en el peor (destino lejano), se consolida todo igual — mejor/peor caso, 02-03.

Solución 3

Pesos reales: A→B = 1; A→C→B = −1 + 1 = 0 ← el más corto. Con K = 2: A→B = 3; A→C→B = 1 + 3 = 4 → el Dijkstra "arreglado" elige A→B. El fallo: la constante K se cobra una vez por tramo, así que penaliza más a los caminos con más tramos — distorsiona la comparación entre caminos de distinta longitud. Sumar K no traslada el problema, lo cambia por otro. Los pesos negativos requieren algoritmos pensados para ellos, no maquillaje; Floyd-Warshall (siguiente lección) es uno.

Dijkstra cumple lo prometido en 03-02: un greedy con demostración. Manteniendo distancias provisionales y consolidando siempre la parada pendiente más cercana — con la garantía, válida solo con pesos no negativos, de que ningún rodeo puede mejorarla — calcula los caminos mínimos desde un origen en O((V+E) log V) gracias a la cola de prioridad de heapq, y el diccionario de predecesoras reconstruye los itinerarios igual que reconstruíamos la mochila en 03-03. La traza desde Plaza Mayor nos enseñó su firma (consolidación en orden de distancia creciente, provisionales que se corrigen por el camino) y el contraejemplo final nos enseñó su frontera: un solo peso negativo y la voracidad vuelve a ser el pecado que era en cambio_greedy. Pero a RutaBus le queda una petición que Dijkstra solo resuelve a fuerza bruta: la web quiere la matriz completa de tiempos entre todas las paradas. ¿Ejecutamos Dijkstra V veces, o hay algo mejor? La respuesta es el algoritmo que anunciamos en 03-03 como "programación dinámica sobre grafos", que además digiere pesos negativos sin pestañear: Floyd-Warshall.