La web de RutaBus vol publicar la taula "minuts mínims entre qualsevol parell de parades": el problema tots-amb-tots (all-pairs shortest paths). Dijkstra (04-05) el resol per força de repetició — un origen cada vegada —, però existeix un algorisme que ataca la matriu completa d'una sola peça, tolera pesos negatius i cap en cinc línies: Floyd-Warshall. És la promesa que vam deixar signada a 03-03: programació dinàmica sobre grafs — un subproblema enginyós ("camí mínim usant només les primeres k parades com a intermèdies"), una taula que s'omple, i la solució que emergeix en completar-la. En aquesta lliçó l'implementarem i traçarem matriu a matriu, aprendrem a detectar cicles negatius mirant una diagonal i a reconstruir camins amb una segona matriu; i, com que és la darrera parada del mòdul, tancarem amb el mapa complet dels sis clàssics i el pont cap a l'optimització.

1. El problema tots-amb-tots: repetir Dijkstra o alguna cosa millor?
2. La idea de programació dinàmica: intermèdies permeses
3. Representació: de diccionari a matriu d'adjacència
4. Implementació: tres bucles i una desigualtat
5. Traça matriu a matriu sobre una xarxa de 4 parades
6. Cicles negatius: la diagonal delatora
7. Complexitat i reconstrucció de camins
8. Tancament del mòdul: els sis clàssics en una taula

L'opció òbvia: executar dijkstra(xarxa, origen) amb cadascuna de les V parades com a origen. És perfectament legítima — i de vegades la millor. Comparem costos (V parades, E trams):

Lectura pràctica: per a la xarxa urbana de RutaBus (dispersa, pesos positius), Dijkstra repetit és asimptòticament millor. Floyd-Warshall guanya quan el graf és dens, quan hi ha pesos negatius (on Dijkstra ni juga), o quan V és moderat (unes 400 parades → 400³ = 6,4·10⁷ operacions simplíssimes: mil·lisegons) i es valora un codi a prova de bugs. Com sempre des de 02-03: no hi ha campió, hi ha context.

Aplicar programació dinàmica (03-03) exigeix trobar el subproblema correcte. El de Floyd-Warshall és una idea brillant. Numerem les parades 0, 1, ..., V−1 i definim:

D_k[i][j] = cost del camí més curt d'i a j usant com a parades intermèdies únicament les de la llista {0, 1, ..., k−1}.

• Cas base, D_0: sense intermèdies permeses, només valen els trams directes — la matriu d'adjacència tal qual.
• Pas recursiu: en autoritzar una intermèdia nova, la parada k, cada camí i→j té dues opcions exhaustives i excloents: o no usa k (i llavors el seu cost continua sent D_k[i][j]) o usa k exactament una vegada — va d'i a k i de k a j, tots dos trams sense usar k com a intermèdia, és a dir, D_k[i][k] + D_k[k][j]. El mínim de totes dues:

• Resposta final: D_V, amb totes les parades autoritzades com a intermèdies: el camí mínim sense restriccions.

És la signatura de la programació dinàmica de 03-03, punt per punt: subproblemes solapats (els D_k[i][k] es reutilitzen en tota la fila d'actualitzacions), subestructura òptima (el millor camí via k es compon de dos millors camins parcials), i tabulació de baix a dalt (de D_0 a D_V). On cost_minim_tab avançava parada a parada per la L2, aquí avancem permís a permís: cada iteració de k no explora camins, autoritza un punt de pas i deixa que la taula es recombini.

El diccionari d'adjacència de 03-04/04-05 és ideal per recórrer veïnes; Floyd-Warshall, en canvi, consulta i actualitza parells (i, j) arbitraris sense parar, així que li convé la matriu d'adjacència: una taula V×V on la cel·la [i][j] guarda el pes del tram directe i→j (∞ si no existeix, 0 a la diagonal).

Prenem la subxarxa de 4 parades de 03-04 amb els minuts de 04-05 — índexs 0 = Plaça Major, 1 = Estació Nord, 2 = Hospital Central, 3 = Parc del Riu:

La matriu és simètrica perquè el graf és no dirigit; amb trams de sentit únic deixaria de ser-ho i res més no canviaria.

L'actualització interior és la relaxació de 04-05 amb un altre vestit: "anar d'i a j passant per k millora el que tinc?". Detalls importants:

• L'ordre dels bucles no és negociable: k ha de ser l'extern. Cada volta de k completa la transició D_k → D_{k+1} per a tota la matriu; posar k dins trenca la definició del subproblema i produeix distàncies incorrectes (és el bug clàssic d'aquest algorisme).
• I no caldria guardar D_k i D_{k+1} en matrius separades? Sorprenentment no: a la volta k, les cel·les dist[i][k] i dist[k][j] no canvien (la millora via k d'un camí que acaba o comença en k passaria dues vegades per k, i això mai no millora sense cicles negatius), així que actualitzar sobre la mateixa matriu és segur. Estalvi d'O(V²) a cost zero — un regal que la tabulació de 03-03 no sempre fa.
• La còpia inicial ([fila[:] for fila in D]) evita el clàssic àlies de llistes imbricades: dist = D no copiaria res, i dist = D[:] copiaria la llista externa però compartiria les files.

Executem sobre la matriu anterior, mostrant la matriu després de cada valor de k. Canvis en negreta.

k = 0 (s'autoritza la Plaça Major com a intermèdia). Quins parells milloren passant per PM? EN↔PR: 4 + 2 = 6 < ∞. Res més (els altres ja tenen directe millor o involucren PM com a extrem):

k = 1 (s'autoritza l'Estació Nord). PM↔HC: 4 + 5 = 9 < ∞ ✔. PR↔HC via EN: 6 + 5 = 11, no millora el directe 8 ✘:

k = 2 (Hospital Central) i k = 3 (Parc del Riu). Es comproven totes les cel·les i... res no millora: per exemple PM→PR via HC costaria 9 + 8 = 17 contra el 2 directe, i PM→HC via PR costaria 2 + 8 = 10 contra el 9 vigent. D₄ = D₂: és la matriu final.

Verificació creuada: la fila de la Plaça Major — 0, 4, 9, 2 — coincideix exactament amb el que Dijkstra va calcular des de la Plaça Major a 04-05. Dos algorismes, dues estratègies mare, una mateixa veritat; executar-los tots dos i comparar és, de passada, una tècnica de testeig excel·lent.

Observa què ha passat a la traça: el camí PM→HC = 9 (que a Dijkstra va requerir descobrir 10 i corregir a 9) aquí simplement va aparèixer quan es va autoritzar la intermèdia adequada (EN, a k = 1). Floyd-Warshall no explora camins: deixa que la taula els compongui.

Floyd-Warshall admet pesos negatius — la relaxació no "consolida" res irrevocablement, així que l'argument que tombava Dijkstra (04-05) no l'afecta. El seu límit és un altre: els cicles de cost total negatiu. Si existeix un cicle la suma de pesos del qual és < 0, fer-hi voltes redueix el cost indefinidament i "el camí més curt" deixa d'existir (tendeix a −∞).

L'elegant és com es detecta: en acabar, n'hi ha prou de mirar la diagonal. dist[i][i] comença en 0 (anar d'i a i sense moure's); si l'algorisme troba dist[i][i] < 0, és que hi ha un camí d'i a i amb cost negatiu — un cicle negatiu assolible des d'i:

A RutaBus els minuts no són negatius i això no aplica; però si els pesos modelessin cost econòmic amb subvencions per tram, un cicle negatiu significaria "ruta circular que genera diners infinits" — senyal inequívoc de dades corruptes o d'un model mal plantejat, i aquesta comprovació d'una línia el delata.

Temps: Θ(V³). Tres bucles imbricats de V voltes amb feina O(1) dins — l'anàlisi línia a línia de 02-01 en la seva forma més pura. Sense millors ni pitjors casos: l'estructura del graf no canvia el recompte (com a màxim canvia quants if disparen l'assignació). Per a la taula web amb V = 200 parades: 8·10⁶ operacions, trivial. Amb V = 100.000... 10¹⁵: mai. El cub posa la frontera en "milers de nodes, no centenars de milers" — la jerarquia de 01-03 manant una altra vegada.

Espai: Θ(V²). La matriu mateixa (gràcies a l'actualització in situ, no hi ha còpia per iteració). És també la mida de la sortida — la taula tots-amb-tots que RutaBus volia publicar —, així que en aquest problema l'espai quadràtic és irreductible.

Reconstruir els camins. Com a Dijkstra (i com a la motxilla de 03-03), el "quant" no basta: cal el "per on". La molla de pa aquí és una matriu de següents: sig[i][j] = primera parada cap a la qual moure's en el camí òptim d'i a j. S'inicialitza amb sig[i][j] = j per a cada tram directe, i cada vegada que la relaxació millora un camí via k, el primer pas cap a j passa a ser el primer pas cap a k:

Davant del diccionari previa de Dijkstra (una molla per parada, cap enrere), aquí la matriu guarda una molla per parell i es recorre cap endavant. O(V²) molles per a O(V²) camins: proporcionat.

Sis lliçons, sis algorismes, i cap peça solta: cada clàssic és l'encarnació d'una estratègia del Mòdul 3, analitzada amb les eines del Mòdul 2.

(El quart pal de 03-04, backtracking, no hi té representant: el seu territori són els problemes sense estructura explotable, on no va néixer cap "clàssic eficient" — aquesta absència també és una lliçó.)

• Posar k com a bucle intern. L'error canònic: el codi corre, retorna una matriu amb bona pinta... amb distàncies incorrectes (subestima rutes que necessiten intermèdies "futures"). k autoritza intermèdies i ha de ser el bucle extern. Test ràpid: a la nostra xarxa, si PM→HC no surt 9, els bucles estan malament.
• Inicialitzar malament la matriu: oblidar els 0 de la diagonal, o usar un "infinit" fals com 999999 que en sumar-se dues vegades desborda la lògica de comparació amb pesos grans. float("inf") suma i compara correctament (inf + 5 == inf); usa'l. I si hi ha trams duplicats a les dades, la cel·la s'ha de quedar amb el mínim.
• Copiar la matriu amb àlies: dist = D o dist = D[:] comparteixen les files (llistes imbricades), i l'algorisme corromprà la matriu d'entrada. La còpia correcta és per files: [fila[:] for fila in D] — cost ocult de Python que ja coneixem de 02-01.
• Usar-lo per comoditat en grafs enormes i dispersos: V³ amb V = 50.000 són 1,25·10¹⁴ operacions. Per a la xarxa nacional de parades, Dijkstra des de cada origen (o només des dels que es consulten) és l'opció; Floyd-Warshall és per a V moderat o dens. La taula de l'apartat 1 és la xuleta.
• Consell: verifica el teu Floyd-Warshall contrastant una fila de la seva matriu amb un Dijkstra des d'aquella parada (si els pesos són ≥ 0). Dues implementacions independents que coincideixen valen més que vint lectures del propi codi.

Afegeix a la matriu de 4 parades un tram de sentit únic Hospital Central → Plaça Major de 3 minuts (la matriu deixa de ser simètrica: només canvia D[2][0] = 3). Executa la traça k = 0..3 i dona la matriu final. Quin parell de parades millora gràcies al tram nou i per què el parell invers no?

Amb la matriu dist i la matriu sig de l'apartat 7 sobre la xarxa original de 4 parades: reconstrueix pas a pas cami(sig, 3, 1) (Parc del Riu → Estació Nord), indicant el valor de sig consultat a cada salt i verificant que els minuts sumen dist[3][1].

RutaBus estudia dos desplegaments: (a) la xarxa urbana amb V = 300 parades i E ≈ 900 trams, matriu completa recalculada cada nit; (b) la xarxa metropolitana amb V = 20.000 i E ≈ 60.000, on només l'1 % dels parells es consulta realment. Per a cada cas, tria entre Floyd-Warshall i Dijkstra-repetit i justifica-ho amb números aproximats (usa log₂ V ≈ 8 per a 300 i ≈ 14 per a 20.000).

Solució 1

Només canvia la cel·la D[2][0] = 3 (HC→PM); D[0][2] continua sent ∞ fins que les intermèdies facin la seva feina. Traça de canvis: amb k = 0 (PM): EN→PR = 6 i PR→EN = 6 com a la xarxa original; HC→EN via PM = 3+4 = 7 no millora el 5 directe ✘; però HC→PR via PM = 3+2 = 5 millora el 8 directe ✔. Amb k = 1 (EN): PM→HC = 4+5 = 9 ✔; en canvi PR→HC via EN = 6+5 = 11 no millora el seu 8 directe ✘ (compte amb l'asimetria: HC→PR sí que va baixar a 5, però PR→HC continua en 8 — són cel·les diferents). Amb k = 2 (HC): EN→PM via HC = 5+3 = 8 ✘ (4 directe), PR→PM via HC = 8+3 = 11 ✘ (2 directe). k = 3: sense canvis. Matriu final:

Millora HC→PR (8 → 5, via PM gràcies a la drecera HC→PM). L'invers PR→HC es queda en 8: el tram nou és de sentit únic i només ajuda els camins que van cap a la Plaça Major. En grafs dirigits, cada sentit viu la seva vida.

Solució 2

Sobre la xarxa original, dist[3][1] = 6 (PR→EN via PM). Inicialment sig[3][1] = None... fins que a k = 0 la millora via PM assigna sig[3][1] = sig[3][0] = 0. Reconstrucció de cami(sig, 3, 1): ruta = [3]; consulta sig[3][1] = 0 → salta a PM, ruta = [3, 0]; consulta sig[0][1] = 1 (tram directe) → salta a EN, ruta = [3, 0, 1]. Camí: Parc del Riu → Plaça Major → Estació Nord; minuts: 2 + 4 = 6 = dist[3][1] ✔.

Solució 3

(a) V = 300: Floyd-Warshall costa 300³ = 2,7·10⁷ operacions elementals — dècimes de segon, codi mínim, i la sortida (la matriu de 9·10⁴ cel·les) és exactament el que es vol publicar. Dijkstra × 300 ≈ 300 · (300+900) · 8 ≈ 2,9·10⁶ — també trivial i una mica menor, però amb més codi i sense avantatge material. Qualsevol dels dos serveix; Floyd-Warshall és defensable per simplicitat. (b) V = 20.000: Floyd-Warshall costaria 20.000³ = 8·10¹² operacions (hores o dies) i 4·10⁸ cel·les de matriu (diversos GB): inviable. Dijkstra des d'un origen ≈ (20.000 + 60.000) · 14 ≈ 1,1·10⁶; fins i tot llançant-lo des dels 200 orígens consultats (l'1 %), ≈ 2,2·10⁸: perfectament assumible, i calculant només el que es consulta. Dijkstra sota demanda, sense discussió. Moralitat: el tots-amb-tots només es materialitza quan de debò es necessita tot.

Floyd-Warshall corona el mòdul demostrant que la programació dinàmica de 03-03 escala a grafs: el subproblema "camí mínim usant només les primeres k parades com a intermèdies" converteix el tots-amb-tots en una taula V×V que tres bucles omplen en Θ(V³), amb actualització in situ, detecció de cicles negatius a la diagonal i una matriu de següents per reconstruir qualsevol itinerari — tot plegat tolerant els pesos negatius que a Dijkstra li estaven vedats, a canvi d'un cub que en limita l'ús a xarxes de mida moderada o denses. Amb ell es completa el repertori: cerca binària i les dues grans ordenacions com a filles de divideix i venceràs, Dijkstra com el greedy demostradament òptim i Floyd-Warshall com la programació dinàmica feta matriu — sis clàssics que ja sabem implementar, traçar, analitzar per casos i, sobretot, triar segons el problema de RutaBus que tinguem davant. Ja sabem triar l'algorisme correcte; el Mòdul 5 comença on aquesta tria acaba: aprendre a esprémer-ne la implementació — optimitzar el codi (05-01), la memòria (05-02) i repartir la feina entre diversos nuclis (05-03) — perquè entre un algorisme ben triat i un programa ràpid encara hi ha un ofici pel mig, i aquest ofici és el que ve ara.