La lección anterior terminó con una espina clavada: BFS asegura que el Hospital está "a 2 tramos" del Almacén… por una avenida congestionada de 16 minutos, cuando existe un camino de 13. Cuando las aristas pesan, contar tramos ya no sirve: hay que sumar minutos. Esta lección presenta los tres algoritmos clásicos de caminos mínimos: Dijkstra (un origen, pesos no negativos — aquí cobramos por fin la semilla del heap que plantamos en 01-04), Bellman-Ford (un origen, admite pesos negativos y detecta ciclos negativos) y Floyd-Warshall (todos los pares, programación dinámica pura, heredera directa de 01-03). Al final construiremos la matriz de tiempos reales entre todas las zonas de Rutalia — la misma clase de matriz que alimentaba las distancias del TSP en el módulo 2.

1. Por qué BFS no basta cuando las aristas pesan
2. Dijkstra: la cola de prioridad cobra su semilla
3. El invariante de Dijkstra y su complejidad
4. Por qué Dijkstra falla con pesos negativos
5. Bellman-Ford: relajar hasta la extenuación
6. Ciclos negativos: cuando el modelo se rompe
7. Floyd-Warshall: todos los pares con programación dinámica
8. La matriz de tiempos de Rutalia y su conexión con el TSP
9. Tabla comparativa y una mención a A*

BFS procesa los nodos por número de aristas desde el origen, y su corrección depende de que descubrir antes = estar más cerca. Con pesos, eso se rompe: en la red canónica, ALM→CEN por la avenida directa es 1 arista y 12 minutos, mientras que ALM→MER→CEN son 2 aristas y 9 minutos. BFS "cierra" CEN en el nivel 1 y nunca reconsidera.

La reparación conceptual es elegante: en vez de procesar los nodos por orden de descubrimiento (cola FIFO), procesarlos por distancia acumulada provisional, siempre el más cercano primero. ¿Qué estructura entrega eficientemente "el mínimo actual" entre candidatos que cambian? Exactamente la que estudiamos en 01-04 para priorizar pedidos: el heap binario (heapq). Dijkstra es, literalmente, BFS con la cola cambiada por un heap.

Desglose línea a línea de las decisiones importantes:

• Tuplas (distancia, nodo) en el heap: heapq ordena tuplas por el primer elemento, así que heappop devuelve siempre el nodo de menor distancia provisional. Es exactamente el patrón "priorizar pedidos urgentes" de 01-04, con la urgencia = minutos acumulados.
• Relajación (nueva < dist[v]): la operación atómica de todos los algoritmos de esta lección. Significa "he encontrado una forma más rápida de llegar a v; actualizo".
• Borrado perezoso (if u in cerrados: continue): heapq no permite actualizar la prioridad de un elemento ya insertado, así que cuando mejoramos dist[v] simplemente insertamos otra entrada. Las versiones viejas (peores) saldrán después y se descartan al ver el nodo ya cerrado. Es la misma técnica de entradas obsoletas que usamos en el mejor-primero del branch and bound (02-03) — no por casualidad: B&B con cota = coste acumulado es un pariente de Dijkstra.
• La reconstrucción de rutas es el reconstruir(padre, destino) de 03-02, sin cambios: ALM→HOS devuelve ['ALM', 'MER', 'CEN', 'HOS'], los 13 minutos reales. La espina de BFS, extraída.

Traza de los primeros pasos, para fijar la intuición (desde ALM):

Fíjate en el paso 2: la avenida directa de 12 minutos queda batida antes de que CEN se cierre. Ese es todo el secreto.

Invariante: cuando un nodo u sale del heap con distancia d (y se cierra), d es la distancia mínima real hasta u. ¿Por qué? Cualquier otro camino hasta u tendría que salir de la zona cerrada atravesando algún nodo frontera w todavía en el heap. Pero ese w tiene distancia provisional ≥ d (si fuera menor, habría salido antes que u), y de w a u solo se pueden sumar pesos no negativos. Total: cualquier alternativa mide ≥ d. No hay sorpresa posible.

Complejidad con lista de adyacencia + heap binario: cada arista provoca a lo sumo una inserción en el heap ⇒ O(m) inserciones/extracciones de coste O(log n) cada una (el heap contiene O(m) entradas, y log m = O(log n)): O((n + m) log n). Para el callejero de una gran ciudad (n ≈ 10⁵, m ≈ 3·10⁵), unos pocos millones de operaciones: milisegundos. La jerarquía de crecimiento de 01-01 en acción.

El argumento del invariante usa una frase con letra pequeña: "solo se pueden sumar pesos no negativos". Si una arista puede restar, cerrar nodos se vuelve prematuro. Ejemplo mínimo con sentido logístico: Rutalia bonifica ciertos tramos donde la furgoneta recoge devoluciones a la vuelta — el coste neto del tramo (tiempo menos ahorro equivalente) puede salir negativo.

Camino real óptimo ALM→HOS: ALM→MER→UNI→HOS = 4 + 6 − 2 = 8. Pero Dijkstra cierra HOS en cuanto sale del heap con 9 (la ruta directa), antes de procesar UNI (que está a 10): cuando la bonificación aparece, HOS ya está cerrado y la mejora se descarta. Resultado de Dijkstra: 9. Incorrecto, y lo peor es que falla en silencio: ni error ni aviso. Con pesos que pueden ser negativos, Dijkstra queda descalificado.

Bellman-Ford renuncia a la astucia del heap y aplica fuerza sistemática: relajar todas las aristas, y repetir la pasada |V| − 1 veces.

¿Por qué |V| − 1 pasadas bastan? Un camino mínimo simple usa a lo sumo |V| − 1 aristas. Tras la pasada k, están garantizados todos los caminos mínimos de hasta k aristas (inducción directa). El precio de esta robustez: O(n · m), muy superior al coste de Dijkstra — en el callejero de 10⁵ nodos hablamos de ~3·10¹⁰ operaciones frente a los milisegundos de Dijkstra. Se paga la generalidad.

Un ciclo negativo es un ciclo cuya suma de pesos es < 0. Si es alcanzable, "camino mínimo" deja de tener sentido: dar una vuelta más siempre mejora, hasta −∞. En Rutalia aparecería si las bonificaciones estuvieran mal calibradas: añade a BONIF la arista HOS→MER con coste −9 y el ciclo MER→UNI→HOS→MER suma 6 − 2 − 9 = −5. Una furgoneta "ganaría minutos" dando vueltas infinitas — señal inequívoca de que el modelo de incentivos está roto, no de que hayamos descubierto el movimiento perpetuo. Por eso la detección de la pasada |V| no es un adorno: es una validación del modelo. (En finanzas, el mismo test detecta oportunidades de arbitraje en ciclos de divisas.)

Dijkstra y Bellman-Ford responden "¿a cuánto está todo desde este origen?". Rutalia necesita algo más ambicioso: la tabla de tiempos entre todas las zonas. Podríamos lanzar Dijkstra desde cada nodo (perfectamente válido: n ejecuciones), pero hay un algoritmo de una elegancia notable que lo hace directamente sobre la matriz de adyacencia de 03-01: Floyd-Warshall.

Su subproblema de PD es una joya de definición (compárese con la cuadrícula de 01-03, donde el subproblema era "mejor coste hasta la celda (i,j)"):

D_k[i][j] = coste mínimo de i a j usando como nodos intermedios solo los k primeros nodos de la lista.

• Caso base D₀: la matriz de adyacencia (sin intermedios: solo aristas directas).
• Transición: al permitir el nodo k como intermedio, o no se usa (queda D_{k−1}[i][j]) o se usa exactamente una vez (D_{k−1}[i][k] + D_{k−1}[k][j]):

Detalles que importan:

• El orden de los bucles es sagrado: k (el intermedio) va fuera. Con k dentro, el algoritmo es simplemente incorrecto. Es el error más frecuente al escribirlo de memoria.
• Como en la PD bottom-up de 01-03, sobreescribimos una única matriz en vez de guardar las n capas D_k: se puede demostrar que reutilizar valores ya actualizados de la capa k no rompe la corrección (solo puede adelantar mejoras válidas).
• Complejidad: tres bucles completos ⇒ O(n³) y memoria O(n²). Para 9 zonas, 729 pasos: nada. Para 1.000 nodos, 10⁹: frontera. Para el callejero entero: inviable — ahí se usan n ejecuciones de Dijkstra sobre lista de adyacencia, o técnicas de 06-03.
• Admite pesos negativos (sin ciclos negativos); un ciclo negativo se delata porque algún D[i][i] acaba < 0. Test gratuito.

Resultado de ejecutar el código sobre la red canónica — la matriz de tiempos mínimos en minutos entre todas las zonas:

Obsérvese: D[ALM][CEN] = 9 (no 12: nadie en su sano juicio usa la avenida congestionada) y D[ALM][HOS] = 13 (el camino de 3 tramos que BFS despreciaba). La matriz es simétrica porque el grafo es no dirigido.

Y aquí se cierra un círculo con el módulo 2: esta matriz es la que alimentaba el TSP. En 02-02 usamos distancias euclídeas entre las 10 paradas por simplicidad didáctica, pero en una ciudad real la furgoneta no vuela en línea recta: la "distancia" entre dos paradas es el tiempo del camino mínimo por las calles. El flujo de trabajo profesional es exactamente este pipeline: (1) grafo viario → (2) Floyd-Warshall o n×Dijkstra → matriz de tiempos → (3) TSP/B&B/GA/ACO sobre esa matriz. Los módulos 2 y 3 no eran temas separados: eran las dos mitades de un mismo sistema.

Guía de elección: sin pesos → BFS; pesos ≥ 0 y un origen → Dijkstra; posibles pesos negativos o necesidad de validar el modelo → Bellman-Ford; todos los pares y n moderado → Floyd-Warshall (o n ejecuciones de Dijkstra si el grafo es disperso y los pesos no negativos).

Una mención de pasada: cuando solo interesa un destino concreto y se dispone de una estimación de lo que falta (por ejemplo, distancia en línea recta), existe A*: esencialmente "Dijkstra con brújula", que orienta la exploración hacia el objetivo en lugar de expandirse en círculo. Pertenece a la búsqueda heurística en espacios de estados y lo desarrollaremos en 04-03; aquí basta saber que su corazón es exactamente el Dijkstra de esta lección.

• Usar Dijkstra con pesos negativos: falla en silencio, como vimos con la bonificación (devuelve 9 en lugar de 8). Añade un assert de pesos no negativos al construir el grafo si vas a usar Dijkstra; es la validación más rentable de esta lección.
• Olvidar el borrado perezoso: sin el if u in cerrados: continue, cada entrada obsoleta del heap reprocesa el nodo y re-relaja sus aristas; el resultado sigue siendo correcto, pero el coste se dispara. Con él, correcto y eficiente.
• Poner el bucle k de Floyd-Warshall en el interior: produce resultados incorrectos difíciles de detectar en grafos pequeños (a veces coincide por suerte). El intermedio k va SIEMPRE fuera. Verifica con la fila ALM de la tabla.
• Parar Bellman-Ford tras |V|−1 pasadas sin la pasada extra: te tragas los ciclos negativos y devuelves distancias sin sentido. La pasada n es la que valida el modelo.
• Recalcular Dijkstra para cada pareja origen-destino de una tabla completa: o bien Floyd-Warshall, o bien un Dijkstra por origen reutilizando su resultado para los n−1 destinos. Nunca n² ejecuciones.
• Consejo: guarda siempre padre además de dist. Una distancia sin su ruta es una respuesta a medias; el repartidor necesita el itinerario, no solo el número.

1. Ruta cotidiana. Usando dijkstra y el reconstruir de 03-02, calcula la ruta más rápida y su duración de EST a PAR en la red canónica. Comprueba el resultado contra la matriz de la lección.
2. La avenida, ¿para quién? La arista ALM–CEN (12 min) parece inútil: Dijkstra nunca la usa desde ALM. Escribe código que, usando la matriz D de Floyd-Warshall, compruebe si la arista pertenece al camino mínimo de algún par de zonas (pista: la arista {u,v} de peso p está en algún camino mínimo entre i y j si D[i][u] + p + D[v][j] == D[i][j], en alguna orientación). ¿Debería Rutalia pedir al ayuntamiento eliminarla del callejero?
3. Bonificación traicionera. Partiendo del grafo BONIF, añade la arista HOS -> MER con coste −9 y verifica que bellman_ford lanza la excepción de ciclo negativo. Después encuentra el coste máximo (menos negativo) que puede tener esa arista sin crear ciclo negativo, razonándolo sobre el ciclo MER→UNI→HOS→MER.

Ejercicio 1:

EST→UNI (3) →HOS (5) →PAR (7) = 15 minutos, que coincide con la celda [EST][PAR] = 15 de la matriz. Dos algoritmos distintos, misma verdad: así se valida software.

Ejercicio 2:

La avenida no participa en el camino mínimo de ningún par: siempre existe alternativa más rápida (como mínimo, rodear por MER o RIO). ¿Eliminarla? No necesariamente: los caminos mínimos son el régimen nominal. Si unas obras cortan MER–CEN y RIO–CEN a la vez, la avenida se convierte en la única entrada rápida al Centro. Redundancia ≠ inutilidad — el análisis de robustez de 03-02 y el de flujo de 03-05 completan la foto que los caminos mínimos solos no dan.

Ejercicio 3:

El ciclo es MER→UNI (6) →HOS (−2) →MER (x), con suma 4 + x. Es negativo si x < −4. Por tanto el coste mínimo admisible de la arista es −4 (con −4 el ciclo suma 0: legal aunque degenerado; con −5 ya es negativo y el modelo se rompe). Moraleja operativa: las bonificaciones de Rutalia deben calibrarse mirando los ciclos del grafo, no cada tramo por separado.

Hemos pasado de contar tramos a sumar minutos. Dijkstra —BFS con el heap de 01-04, semilla cobrada— resuelve el caso estándar con pesos no negativos en O((n+m) log n) gracias a un invariante voraz que se demuestra en tres líneas; Bellman-Ford paga O(n·m) a cambio de tolerar bonificaciones negativas y de detectar ciclos negativos, que son errores de modelo disfrazados de chollos; y Floyd-Warshall, programación dinámica sobre la matriz con el nodo intermedio como dimensión, entrega en O(n³) la matriz completa de tiempos de Rutalia — la pieza que conecta este módulo con el TSP del módulo 2: primero caminos mínimos sobre el callejero, después optimización de rutas sobre la matriz resultante. Dijkstra nos ha enseñado además algo más profundo: que un algoritmo voraz puede ser demostrablemente óptimo si el problema tiene la estructura adecuada. En 02-02 vimos voraces que fracasaban; en la próxima lección, 03-04, veremos el otro caso estrella donde la avaricia gana con certificado: los árboles de expansión mínima, con Kruskal —hora de cobrar la segunda semilla de 01-04, el union-find— y Prim.