La web de RutaBus quiere publicar la tabla "minutos mínimos entre cualquier par de paradas": el problema todos-con-todos (all-pairs shortest paths). Dijkstra (04-05) lo resuelve por fuerza de repetición — un origen cada vez —, pero existe un algoritmo que ataca la matriz completa de una sola pieza, tolera pesos negativos y cabe en cinco líneas: Floyd-Warshall. Es la promesa que dejamos firmada en 03-03: programación dinámica sobre grafos — un subproblema ingenioso ("camino mínimo usando solo las primeras k paradas como intermedias"), una tabla que se rellena, y la solución que emerge al completarla. En esta lección lo implementaremos y trazaremos matriz a matriz, aprenderemos a detectar ciclos negativos mirando una diagonal y a reconstruir caminos con una segunda matriz; y, como es la última parada del módulo, cerraremos con el mapa completo de los seis clásicos y el puente hacia la optimización.

1. El problema todos-con-todos: ¿repetir Dijkstra o algo mejor?
2. La idea de programación dinámica: intermedias permitidas
3. Representación: de diccionario a matriz de adyacencia
4. Implementación: tres bucles y una desigualdad
5. Traza matriz a matriz sobre una red de 4 paradas
6. Ciclos negativos: la diagonal delatora
7. Complejidad y reconstrucción de caminos
8. Cierre del módulo: los seis clásicos en una tabla

La opción obvia: ejecutar dijkstra(red, origen) con cada una de las V paradas como origen. Es perfectamente legítima — y a veces la mejor. Comparemos costes (V paradas, E tramos):

Lectura práctica: para la red urbana de RutaBus (dispersa, pesos positivos), Dijkstra repetido es asintóticamente mejor. Floyd-Warshall gana cuando el grafo es denso, cuando hay pesos negativos (donde Dijkstra ni juega), o cuando V es moderado (unas 400 paradas → 400³ = 6,4·10⁷ operaciones simplísimas: milisegundos) y se valora un código a prueba de bugs. Como siempre desde 02-03: no hay campeón, hay contexto.

Aplicar programación dinámica (03-03) exige encontrar el subproblema correcto. El de Floyd-Warshall es una idea brillante. Numeramos las paradas 0, 1, ..., V−1 y definimos:

D_k[i][j] = coste del camino más corto de i a j usando como paradas intermedias únicamente las de la lista {0, 1, ..., k−1}.

• Caso base, D_0: sin intermedias permitidas, solo valen los tramos directos — la matriz de adyacencia tal cual.
• Paso recursivo: al autorizar una intermedia nueva, la parada k, cada camino i→j tiene dos opciones exhaustivas y excluyentes: o no usa k (y entonces su coste sigue siendo D_k[i][j]) o usa k exactamente una vez — va de i a k y de k a j, ambos tramos sin usar k como intermedia, es decir, D_k[i][k] + D_k[k][j]. El mínimo de ambas:

• Respuesta final: D_V, con todas las paradas autorizadas como intermedias: el camino mínimo sin restricciones.

Es la firma de la programación dinámica de 03-03, punto por punto: subproblemas solapados (los D_k[i][k] se reutilizan en toda la fila de actualizaciones), subestructura óptima (el mejor camino vía k se compone de dos mejores caminos parciales), y tabulación de abajo arriba (de D_0 a D_V). Donde coste_minimo_tab avanzaba parada a parada por la L2, aquí avanzamos permiso a permiso: cada iteración de k no explora caminos, autoriza un punto de paso y deja que la tabla se recombine.

El diccionario de adyacencia de 03-04/04-05 es ideal para recorrer vecinas; Floyd-Warshall, en cambio, consulta y actualiza pares (i, j) arbitrarios sin parar, así que le conviene la matriz de adyacencia: una tabla V×V donde la celda [i][j] guarda el peso del tramo directo i→j (∞ si no existe, 0 en la diagonal).

Tomemos la subred de 4 paradas de 03-04 con los minutos de 04-05 — índices 0 = Plaza Mayor, 1 = Estación Norte, 2 = Hospital Central, 3 = Parque del Río:

La matriz es simétrica porque el grafo es no dirigido; con tramos de sentido único dejaría de serlo y nada más cambiaría.

La actualización interior es la relajación de 04-05 con otro ropaje: "¿ir de i a j pasando por k mejora lo que tengo?". Detalles importantes:

• El orden de los bucles no es negociable: k debe ser el externo. Cada vuelta de k completa la transición D_k → D_{k+1} para toda la matriz; poner k dentro rompe la definición del subproblema y produce distancias incorrectas (es el bug clásico de este algoritmo).
• ¿Y no habría que guardar D_k y D_{k+1} en matrices separadas? Sorprendentemente no: en la vuelta k, las celdas dist[i][k] y dist[k][j] no cambian (la mejora vía k de un camino que acaba o empieza en k pasaría dos veces por k, y eso nunca mejora sin ciclos negativos), así que actualizar sobre la propia matriz es seguro. Ahorro de O(V²) a coste cero — un regalo que la tabulación de 03-03 no siempre hace.
• La copia inicial ([fila[:] for fila in D]) evita el clásico alias de listas anidadas: dist = D no copiaría nada, y dist = D[:] copiaría la lista externa pero compartiría las filas.

Ejecutemos sobre la matriz anterior, mostrando la matriz después de cada valor de k. Cambios en negrita.

k = 0 (se autoriza Plaza Mayor como intermedia). ¿Qué pares mejoran pasando por PM? EN↔PR: 4 + 2 = 6 < ∞. Nada más (los demás ya tienen directo mejor o involucran a PM como extremo):

k = 1 (se autoriza Estación Norte). PM↔HC: 4 + 5 = 9 < ∞ ✔. PR↔HC vía EN: 6 + 5 = 11, no mejora el directo 8 ✘:

k = 2 (Hospital Central) y k = 3 (Parque del Río). Se comprueban todas las celdas y... nada mejora: por ejemplo PM→PR vía HC costaría 9 + 8 = 17 contra el 2 directo, y PM→HC vía PR costaría 2 + 8 = 10 contra el 9 vigente. D₄ = D₂: es la matriz final.

Verificación cruzada: la fila de Plaza Mayor — 0, 4, 9, 2 — coincide exactamente con lo que Dijkstra calculó desde Plaza Mayor en 04-05. Dos algoritmos, dos estrategias madre, una misma verdad; ejecutar ambos y comparar es, de paso, una técnica de testeo excelente.

Obsérvese lo que ha pasado en la traza: el camino PM→HC = 9 (que en Dijkstra requirió descubrir 10 y corregir a 9) aquí simplemente apareció cuando se autorizó la intermedia adecuada (EN, en k = 1). Floyd-Warshall no explora caminos: deja que la tabla los componga.

Floyd-Warshall admite pesos negativos — la relajación no "consolida" nada irrevocablemente, así que el argumento que tumbaba a Dijkstra (04-05) no le afecta. Su límite es otro: los ciclos de coste total negativo. Si existe un ciclo cuya suma de pesos es < 0, dar vueltas por él reduce el coste indefinidamente y "el camino más corto" deja de existir (tiende a −∞).

Lo elegante es cómo se detecta: al terminar, basta mirar la diagonal. dist[i][i] empieza en 0 (ir de i a i sin moverse); si el algoritmo encuentra dist[i][i] < 0, es que hay un camino de i a i con coste negativo — un ciclo negativo alcanzable desde i:

En RutaBus los minutos no son negativos y esto no aplica; pero si los pesos modelaran coste económico con subvenciones por tramo, un ciclo negativo significaría "ruta circular que genera dinero infinito" — señal inequívoca de datos corruptos o de un modelo mal planteado, y este chequeo de una línea lo delata.

Tiempo: Θ(V³). Tres bucles anidados de V vueltas con trabajo O(1) dentro — el análisis línea a línea de 02-01 en su forma más pura. Sin mejores ni peores casos: la estructura del grafo no cambia el recuento (a lo sumo cambia cuántos if disparan la asignación). Para la tabla web con V = 200 paradas: 8·10⁶ operaciones, trivial. Con V = 100.000... 10¹⁵: jamás. El cubo pone la frontera en "miles de nodos, no cientos de miles" — la jerarquía de 01-03 mandando otra vez.

Espacio: Θ(V²). La matriz misma (gracias a la actualización in-place, no hay copia por iteración). Es también el tamaño de la salida — la tabla todos-con-todos que RutaBus quería publicar —, así que en este problema el espacio cuadrático es irreducible.

Reconstruir los caminos. Como en Dijkstra (y como en la mochila de 03-03), el "cuánto" no basta: hace falta el "por dónde". La miga de pan aquí es una matriz de siguientes: sig[i][j] = primera parada a la que moverse en el camino óptimo de i a j. Se inicializa con sig[i][j] = j para cada tramo directo, y cada vez que la relajación mejora un camino vía k, el primer paso hacia j pasa a ser el primer paso hacia k:

Frente al diccionario previa de Dijkstra (una miga por parada, hacia atrás), aquí la matriz guarda una miga por par y se recorre hacia delante. O(V²) migas para O(V²) caminos: proporcionado.

Seis lecciones, seis algoritmos, y ninguna pieza suelta: cada clásico es la encarnación de una estrategia del Módulo 3, analizada con las herramientas del Módulo 2.

(El cuarto palo de 03-04, backtracking, no tiene representante aquí: su territorio son los problemas sin estructura explotable, donde no nació ningún "clásico eficiente" — esa ausencia también es una lección.)

• Poner k como bucle interno. El error canónico: el código corre, devuelve una matriz con buena pinta... con distancias incorrectas (subestima rutas que necesitan intermedias "futuras"). k autoriza intermedias y debe ser el bucle externo. Test rápido: en nuestra red, si PM→HC no sale 9, los bucles están mal.
• Inicializar mal la matriz: olvidar los 0 de la diagonal, o usar un "infinito" falso como 999999 que al sumarse dos veces desborda la lógica de comparación con pesos grandes. float("inf") suma y compara correctamente (inf + 5 == inf); úsalo. Y si hay tramos duplicados en los datos, la celda debe quedarse con el mínimo.
• Copiar la matriz con alias: dist = D o dist = D[:] comparten las filas (listas anidadas), y el algoritmo corromperá la matriz de entrada. La copia correcta es por filas: [fila[:] for fila in D] — coste oculto de Python que ya conocemos de 02-01.
• Usarlo por comodidad en grafos enormes y dispersos: V³ con V = 50.000 son 1,25·10¹⁴ operaciones. Para la red nacional de paradas, Dijkstra desde cada origen (o solo desde los que se consultan) es la opción; Floyd-Warshall es para V moderado o denso. La tabla del apartado 1 es la chuleta.
• Consejo: verifica tu Floyd-Warshall contrastando una fila de su matriz con un Dijkstra desde esa parada (si los pesos son ≥ 0). Dos implementaciones independientes que coinciden valen más que veinte lecturas del propio código.

Añade a la matriz de 4 paradas un tramo de sentido único Hospital Central → Plaza Mayor de 3 minutos (la matriz deja de ser simétrica: solo cambia D[2][0] = 3). Ejecuta la traza k = 0..3 y da la matriz final. ¿Qué par de paradas mejora gracias al nuevo tramo y por qué el par inverso no?

Con la matriz dist y la matriz sig del apartado 7 sobre la red original de 4 paradas: reconstruye paso a paso camino(sig, 3, 1) (Parque del Río → Estación Norte), indicando el valor de sig consultado en cada salto y verificando que los minutos suman dist[3][1].

RutaBus estudia dos despliegues: (a) la red urbana con V = 300 paradas y E ≈ 900 tramos, matriz completa recalculada cada noche; (b) la red metropolitana con V = 20.000 y E ≈ 60.000, donde solo el 1 % de los pares se consulta realmente. Para cada caso, elige entre Floyd-Warshall y Dijkstra-repetido y justifica con números aproximados (usa log₂ V ≈ 8 para 300 y ≈ 14 para 20.000).

Solución 1

Solo cambia la celda D[2][0] = 3 (HC→PM); D[0][2] sigue siendo ∞ hasta que las intermedias hagan su trabajo. Traza de cambios: con k = 0 (PM): EN→PR = 6 y PR→EN = 6 como en la red original; HC→EN vía PM = 3+4 = 7 no mejora el 5 directo ✘; pero HC→PR vía PM = 3+2 = 5 mejora el 8 directo ✔. Con k = 1 (EN): PM→HC = 4+5 = 9 ✔; en cambio PR→HC vía EN = 6+5 = 11 no mejora su 8 directo ✘ (cuidado con la asimetría: HC→PR sí bajó a 5, pero PR→HC sigue en 8 — son celdas distintas). Con k = 2 (HC): EN→PM vía HC = 5+3 = 8 ✘ (4 directo), PR→PM vía HC = 8+3 = 11 ✘ (2 directo). k = 3: sin cambios. Matriz final:

Mejora HC→PR (8 → 5, vía PM gracias al atajo HC→PM). El inverso PR→HC se queda en 8: el tramo nuevo es de sentido único y solo ayuda a los caminos que van hacia Plaza Mayor. En grafos dirigidos, cada sentido vive su vida.

Solución 2

Sobre la red original, dist[3][1] = 6 (PR→EN vía PM). Inicialmente sig[3][1] = None... hasta que en k = 0 la mejora vía PM asigna sig[3][1] = sig[3][0] = 0. Reconstrucción de camino(sig, 3, 1): ruta = [3]; consulta sig[3][1] = 0 → salta a PM, ruta = [3, 0]; consulta sig[0][1] = 1 (tramo directo) → salta a EN, ruta = [3, 0, 1]. Camino: Parque del Río → Plaza Mayor → Estación Norte; minutos: 2 + 4 = 6 = dist[3][1] ✔.

Solución 3

(a) V = 300: Floyd-Warshall cuesta 300³ = 2,7·10⁷ operaciones elementales — décimas de segundo, código mínimo, y la salida (la matriz de 9·10⁴ celdas) es exactamente lo que se quiere publicar. Dijkstra × 300 ≈ 300 · (300+900) · 8 ≈ 2,9·10⁶ — también trivial y algo menor, pero con más código y sin ventaja material. Cualquiera vale; Floyd-Warshall es defendible por simplicidad. (b) V = 20.000: Floyd-Warshall costaría 20.000³ = 8·10¹² operaciones (horas o días) y 4·10⁸ celdas de matriz (varios GB): inviable. Dijkstra desde un origen ≈ (20.000 + 60.000) · 14 ≈ 1,1·10⁶; incluso lanzándolo desde los 200 orígenes consultados (el 1 %), ≈ 2,2·10⁸: perfectamente asumible, y calculando solo lo que se consulta. Dijkstra bajo demanda, sin discusión. Moraleja: el todos-con-todos solo se materializa cuando de verdad se necesita todo.

Floyd-Warshall corona el módulo demostrando que la programación dinámica de 03-03 escala a grafos: el subproblema "camino mínimo usando solo las primeras k paradas como intermedias" convierte el todos-con-todos en una tabla V×V que tres bucles rellenan en Θ(V³), con actualización in-place, detección de ciclos negativos en la diagonal y una matriz de siguientes para reconstruir cualquier itinerario — todo ello tolerando los pesos negativos que a Dijkstra le estaban vedados, a cambio de un cubo que limita su uso a redes de tamaño moderado o denso. Con él se completa el repertorio: búsqueda binaria y los dos grandes ordenamientos como hijos de divide y vencerás, Dijkstra como el greedy demostradamente óptimo y Floyd-Warshall como la programación dinámica hecha matriz — seis clásicos que ya sabemos implementar, trazar, analizar por casos y, sobre todo, elegir según el problema de RutaBus que tengamos delante. Ya sabemos elegir el algoritmo correcto; el Módulo 5 empieza donde esa elección termina: aprender a exprimir su implementación — optimizar el código (05-01), la memoria (05-02) y repartir el trabajo entre varios núcleos (05-03) — porque entre un algoritmo bien elegido y un programa rápido todavía media un oficio, y ese oficio es el que viene ahora.