La lliçó anterior va acabar amb una espina clavada: BFS assegura que l'Hospital és "a 2 trams" del Magatzem… per una avinguda congestionada de 16 minuts, quan existeix un camí de 13. Quan les arestes pesen, comptar trams ja no serveix: cal sumar minuts. Aquesta lliçó presenta els tres algorismes clàssics de camins mínims: Dijkstra (un origen, pesos no negatius — aquí collim per fi la llavor del heap que vam plantar a 01-04), Bellman-Ford (un origen, admet pesos negatius i detecta cicles negatius) i Floyd-Warshall (tots els parells, programació dinàmica pura, hereva directa de 01-03). Al final construirem la matriu de temps reals entre totes les zones de Rutalia — la mateixa classe de matriu que alimentava les distàncies del TSP al mòdul 2.

1. Per què BFS no basta quan les arestes pesen
2. Dijkstra: la cua de prioritat cull la seva llavor
3. L'invariant de Dijkstra i la seva complexitat
4. Per què Dijkstra falla amb pesos negatius
5. Bellman-Ford: relaxar fins a l'extenuació
6. Cicles negatius: quan el model es trenca
7. Floyd-Warshall: tots els parells amb programació dinàmica
8. La matriu de temps de Rutalia i la seva connexió amb el TSP
9. Taula comparativa i una menció a A*

BFS processa els nodes per nombre d'arestes des de l'origen, i la seva correcció depèn que descobrir abans = ser més a prop. Amb pesos, això es trenca: a la xarxa canònica, ALM→CEN per l'avinguda directa és 1 aresta i 12 minuts, mentre que ALM→MER→CEN són 2 arestes i 9 minuts. BFS "tanca" CEN al nivell 1 i mai no ho reconsidera.

La reparació conceptual és elegant: en lloc de processar els nodes per ordre de descobriment (cua FIFO), processar-los per distància acumulada provisional, sempre el més proper primer. Quina estructura lliura eficientment "el mínim actual" entre candidats que canvien? Exactament la que vam estudiar a 01-04 per prioritzar comandes: el heap binari (heapq). Dijkstra és, literalment, BFS amb la cua canviada per un heap.

Desglossament línia a línia de les decisions importants:

• Tuples (distancia, node) al heap: heapq ordena les tuples pel primer element, així que heappop retorna sempre el node de menor distància provisional. És exactament el patró "prioritzar comandes urgents" de 01-04, amb la urgència = minuts acumulats.
• Relaxació (nova < dist[v]): l'operació atòmica de tots els algorismes d'aquesta lliçó. Significa "he trobat una manera més ràpida d'arribar a v; actualitzo".
• Esborrat mandrós (if u in tancats: continue): heapq no permet actualitzar la prioritat d'un element ja inserit, així que quan millorem dist[v] simplement inserim una altra entrada. Les versions velles (pitjors) sortiran després i es descarten en veure el node ja tancat. És la mateixa tècnica d'entrades obsoletes que vam usar al millor-primer del branch and bound (02-03) — no pas per casualitat: B&B amb fita = cost acumulat és un parent de Dijkstra.
• La reconstrucció de rutes és el reconstruir(pare, desti) de 03-02, sense canvis: ALM→HOS retorna ['ALM', 'MER', 'CEN', 'HOS'], els 13 minuts reals. L'espina de BFS, extreta.

Traça dels primers passos, per fixar la intuïció (des d'ALM):

Fixa't en el pas 2: l'avinguda directa de 12 minuts queda batuda abans que CEN es tanqui. Aquest és tot el secret.

Invariant: quan un node u surt del heap amb distància d (i es tanca), d és la distància mínima real fins a u. Per què? Qualsevol altre camí fins a u hauria de sortir de la zona tancada travessant algun node frontera w encara al heap. Però aquell w té distància provisional ≥ d (si fos menor, hauria sortit abans que u), i de w a u només es poden sumar pesos no negatius. Total: qualsevol alternativa mesura ≥ d. No hi ha sorpresa possible.

Complexitat amb llista d'adjacència + heap binari: cada aresta provoca com a molt una inserció al heap ⇒ O(m) insercions/extraccions de cost O(log n) cadascuna (el heap conté O(m) entrades, i log m = O(log n)): O((n + m) log n). Per a la xarxa de carrers d'una gran ciutat (n ≈ 10⁵, m ≈ 3·10⁵), uns pocs milions d'operacions: mil·lisegons. La jerarquia de creixement de 01-01 en acció.

L'argument de l'invariant fa servir una frase amb lletra petita: "només es poden sumar pesos no negatius". Si una aresta pot restar, tancar nodes esdevé prematur. Exemple mínim amb sentit logístic: Rutalia bonifica certs trams on la furgoneta recull devolucions a la tornada — el cost net del tram (temps menys estalvi equivalent) pot sortir negatiu.

Camí real òptim ALM→HOS: ALM→MER→UNI→HOS = 4 + 6 − 2 = 8. Però Dijkstra tanca HOS tan bon punt surt del heap amb 9 (la ruta directa), abans de processar UNI (que és a 10): quan la bonificació apareix, HOS ja està tancat i la millora es descarta. Resultat de Dijkstra: 9. Incorrecte, i el pitjor és que falla en silenci: ni error ni avís. Amb pesos que poden ser negatius, Dijkstra queda desqualificat.

Bellman-Ford renuncia a l'astúcia del heap i aplica força sistemàtica: relaxar totes les arestes, i repetir la passada |V| − 1 vegades.

Per què n'hi ha prou amb |V| − 1 passades? Un camí mínim simple usa com a molt |V| − 1 arestes. Després de la passada k, estan garantits tots els camins mínims de fins a k arestes (inducció directa). El preu d'aquesta robustesa: O(n · m), molt superior al cost de Dijkstra — a la xarxa de carrers de 10⁵ nodes parlem de ~3·10¹⁰ operacions davant dels mil·lisegons de Dijkstra. Es paga la generalitat.

Un cicle negatiu és un cicle la suma de pesos del qual és < 0. Si és abastable, "camí mínim" deixa de tenir sentit: fer una volta més sempre millora, fins a −∞. A Rutalia apareixeria si les bonificacions estiguessin mal calibrades: afegeix a BONIF l'aresta HOS→MER amb cost −9 i el cicle MER→UNI→HOS→MER suma 6 − 2 − 9 = −5. Una furgoneta "guanyaria minuts" fent voltes infinites — senyal inequívoc que el model d'incentius està trencat, no pas que hàgim descobert el moviment perpetu. Per això la detecció de la passada |V| no és un ornament: és una validació del model. (En finances, el mateix test detecta oportunitats d'arbitratge en cicles de divises.)

Dijkstra i Bellman-Ford responen "a quina distància és tot des d'aquest origen?". Rutalia necessita alguna cosa més ambiciosa: la taula de temps entre totes les zones. Podríem llançar Dijkstra des de cada node (perfectament vàlid: n execucions), però hi ha un algorisme d'una elegància notable que ho fa directament sobre la matriu d'adjacència de 03-01: Floyd-Warshall.

El seu subproblema de PD és una joia de definició (compareu-lo amb la quadrícula de 01-03, on el subproblema era "millor cost fins a la casella (i,j)"):

D_k[i][j] = cost mínim d'i a j usant com a nodes intermedis només els k primers nodes de la llista.

• Cas base D₀: la matriu d'adjacència (sense intermedis: només arestes directes).
• Transició: en permetre el node k com a intermedi, o no s'usa (queda D_{k−1}[i][j]) o s'usa exactament una vegada (D_{k−1}[i][k] + D_{k−1}[k][j]):

Detalls que importen:

• L'ordre dels bucles és sagrat: k (l'intermedi) va fora. Amb k a dins, l'algorisme és simplement incorrecte. És l'error més freqüent en escriure'l de memòria.
• Com a la PD bottom-up de 01-03, sobreescrivim una única matriu en lloc de guardar les n capes D_k: es pot demostrar que reutilitzar valors ja actualitzats de la capa k no trenca la correcció (només pot avançar millores vàlides).
• Complexitat: tres bucles complets ⇒ O(n³) i memòria O(n²). Per a 9 zones, 729 passos: no res. Per a 1.000 nodes, 10⁹: frontera. Per a la xarxa de carrers sencera: inviable — allà s'usen n execucions de Dijkstra sobre llista d'adjacència, o tècniques de 06-03.
• Admet pesos negatius (sense cicles negatius); un cicle negatiu es delata perquè algun D[i][i] acaba < 0. Test gratuït.

Resultat d'executar el codi sobre la xarxa canònica — la matriu de temps mínims en minuts entre totes les zones:

Observeu-ho: D[ALM][CEN] = 9 (no pas 12: ningú amb dos dits de front no fa servir l'avinguda congestionada) i D[ALM][HOS] = 13 (el camí de 3 trams que BFS menyspreava). La matriu és simètrica perquè el graf és no dirigit.

I aquí es tanca un cercle amb el mòdul 2: aquesta matriu és la que alimentava el TSP. A 02-02 vam usar distàncies euclidianes entre les 10 parades per simplicitat didàctica, però en una ciutat real la furgoneta no vola en línia recta: la "distància" entre dues parades és el temps del camí mínim pels carrers. El flux de treball professional és exactament aquest pipeline: (1) graf viari → (2) Floyd-Warshall o n×Dijkstra → matriu de temps → (3) TSP/B&B/GA/ACO sobre aquesta matriu. Els mòduls 2 i 3 no eren temes separats: eren les dues meitats d'un mateix sistema.

Guia d'elecció: sense pesos → BFS; pesos ≥ 0 i un origen → Dijkstra; possibles pesos negatius o necessitat de validar el model → Bellman-Ford; tots els parells i n moderat → Floyd-Warshall (o n execucions de Dijkstra si el graf és dispers i els pesos no negatius).

Una menció de passada: quan només interessa un destí concret i es disposa d'una estimació del que falta (per exemple, distància en línia recta), existeix A*: essencialment "Dijkstra amb brúixola", que orienta l'exploració cap a l'objectiu en lloc d'expandir-se en cercle. Pertany a la cerca heurística en espais d'estats i el desenvoluparem a 04-03; aquí n'hi ha prou de saber que el seu cor és exactament el Dijkstra d'aquesta lliçó.

• Usar Dijkstra amb pesos negatius: falla en silenci, com hem vist amb la bonificació (retorna 9 en lloc de 8). Afegeix un assert de pesos no negatius en construir el graf si has d'usar Dijkstra; és la validació més rendible d'aquesta lliçó.
• Oblidar l'esborrat mandrós: sense el if u in tancats: continue, cada entrada obsoleta del heap reprocessa el node i re-relaxa les seves arestes; el resultat segueix sent correcte, però el cost es dispara. Amb ell, correcte i eficient.
• Posar el bucle k de Floyd-Warshall a l'interior: produeix resultats incorrectes difícils de detectar en grafs petits (a vegades coincideix per sort). L'intermedi k va SEMPRE fora. Verifica-ho amb la fila ALM de la taula.
• Aturar Bellman-Ford després de |V|−1 passades sense la passada extra: t'empasses els cicles negatius i retornes distàncies sense sentit. La passada n és la que valida el model.
• Recalcular Dijkstra per a cada parella origen-destí d'una taula completa: o bé Floyd-Warshall, o bé un Dijkstra per origen reutilitzant el seu resultat per als n−1 destins. Mai n² execucions.
• Consell: guarda sempre pare a més de dist. Una distància sense la seva ruta és una resposta a mitges; el repartidor necessita l'itinerari, no només el número.

1. Ruta quotidiana. Usant dijkstra i el reconstruir de 03-02, calcula la ruta més ràpida i la seva durada d'EST a PAR a la xarxa canònica. Comprova el resultat contra la matriu de la lliçó.
2. L'avinguda, per a qui? L'aresta ALM–CEN (12 min) sembla inútil: Dijkstra mai no la fa servir des d'ALM. Escriu codi que, usant la matriu D de Floyd-Warshall, comprovi si l'aresta pertany al camí mínim d'algun parell de zones (pista: l'aresta {u,v} de pes p és en algun camí mínim entre i i j si D[i][u] + p + D[v][j] == D[i][j], en alguna orientació). Hauria Rutalia de demanar a l'ajuntament que l'elimini del mapa de carrers?
3. Bonificació traïdora. Partint del graf BONIF, afegeix l'aresta HOS -> MER amb cost −9 i verifica que bellman_ford llança l'excepció de cicle negatiu. Després troba el cost màxim (menys negatiu) que pot tenir aquesta aresta sense crear cicle negatiu, raonant-ho sobre el cicle MER→UNI→HOS→MER.

Exercici 1:

EST→UNI (3) →HOS (5) →PAR (7) = 15 minuts, que coincideix amb la cel·la [EST][PAR] = 15 de la matriu. Dos algorismes diferents, mateixa veritat: així es valida el programari.

Exercici 2:

L'avinguda no participa en el camí mínim de cap parell: sempre existeix una alternativa més ràpida (com a mínim, fer la volta per MER o RIO). Eliminar-la? No necessàriament: els camins mínims són el règim nominal. Si unes obres tallen MER–CEN i RIO–CEN alhora, l'avinguda es converteix en l'única entrada ràpida al Centre. Redundància ≠ inutilitat — l'anàlisi de robustesa de 03-02 i la de flux de 03-05 completen la foto que els camins mínims sols no donen.

Exercici 3:

El cicle és MER→UNI (6) →HOS (−2) →MER (x), amb suma 4 + x. És negatiu si x < −4. Per tant el cost mínim admissible de l'aresta és −4 (amb −4 el cicle suma 0: legal encara que degenerat; amb −5 ja és negatiu i el model es trenca). Moralitat operativa: les bonificacions de Rutalia s'han de calibrar mirant els cicles del graf, no cada tram per separat.

Hem passat de comptar trams a sumar minuts. Dijkstra —BFS amb el heap de 01-04, llavor collida— resol el cas estàndard amb pesos no negatius en O((n+m) log n) gràcies a un invariant voraç que es demostra en tres línies; Bellman-Ford paga O(n·m) a canvi de tolerar bonificacions negatives i de detectar cicles negatius, que són errors de model disfressats de gangues; i Floyd-Warshall, programació dinàmica sobre la matriu amb el node intermedi com a dimensió, lliura en O(n³) la matriu completa de temps de Rutalia — la peça que connecta aquest mòdul amb el TSP del mòdul 2: primer camins mínims sobre la xarxa de carrers, després optimització de rutes sobre la matriu resultant. Dijkstra ens ha ensenyat, a més, una cosa més profunda: que un algorisme voraç pot ser demostrablement òptim si el problema té l'estructura adequada. A 02-02 vam veure voraços que fracassaven; a la propera lliçó, 03-04, veurem l'altre cas estrella on l'estratègia voraç guanya amb certificat: els arbres d'expansió mínims, amb Kruskal —hora de collir la segona llavor de 01-04, l'union-find— i Prim.