Deixem les llistes i tornem a la xarxa de parades que vam modelar com a graf a 03-04 — aquesta vegada amb la pregunta estrella de qualsevol app de mobilitat: quants minuts es triga, com a mínim, d'una parada a cadascuna de les altres? L'algorisme que la respon el vam anunciar a 03-02 amb nom i cognom: Dijkstra, "el greedy que sí que és òptim". Després de veure estratègies voraces que fallaven (canvi_greedy, recorregut_supervisor), aquí estudiarem la que triomfa: per què la seva tria voraç — consolidar sempre la parada més propera pendent — és irrevocablement correcta quan els pesos no són negatius, com implementar-la eficientment amb una cua de prioritat (heapq), i com reconstruir el camí a més del seu cost. El traçarem complet des de la Plaça Major i tancarem amb la seva complexitat i la seva única criptonita: els pesos negatius.

1. La xarxa de RutaBus com a graf ponderat
2. El problema: camins més curts des d'un origen
3. La idea greedy i per què funciona
4. Quadre previ: què és un heap / cua de prioritat
5. Implementació amb heapq
6. Traça completa des de la Plaça Major
7. Reconstruir el camí: predecessors
8. Complexitat i la limitació dels pesos negatius

A 03-04 la xarxa era un diccionari d'adjacència que només deia qui connecta amb qui. Per parlar de temps hi hem d'afegir pesos: els minuts de trajecte de cada tram. N'hi ha prou de canviar les llistes de veïnes per diccionaris veina → minuts:

Vocabulari mínim: les parades són els vèrtexs (V = 5), els trams són les arestes (E = 6) i els minuts, els seus pesos. El nostre graf és no dirigit — cada tram apareix en tots dos sentits amb el mateix pes —; si la L3 tingués un tram de sentit únic, n'hi hauria prou d'anotar-lo només en una direcció, i tot el que segueix funcionaria igual.

El cost d'un camí és la suma dels pesos dels seus trams. De la Plaça Major a l'Hospital Central n'hi ha diversos: per l'Estació Nord (4 + 5 = 9), pel Parc del Riu directe (2 + 8 = 10), pel Parc del Riu i la Universitat (2 + 3 + 6 = 11). El problema del camí més curt des d'un origen (single-source shortest paths) demana, per a un origen donat, la distància mínima a totes les altres parades — exactament el que RutaBus necessita per respondre "quant trigo des d'aquí?" a un usuari plantat a la Plaça Major.

Per què no serveix res del que ja tenim? El backtracking de 03-04 (rutes_inspeccio) enumeraria tots els camins possibles — exponencial. I compte amb la trampa d'"el camí amb menys parades": el tram directe PR→HC (8 min) perd contra el tomb PR→UNI→HC (9 min... no, 3+6=9, aquí guanya el directe — però PM→HC per EN amb dos trams guanya al directe per PR amb dos trams). Menys trams no implica menys minuts: cal comptar pesos, no salts. (Comptar salts és el que faria una cerca en amplada, BFS — una línia de menció i seguim, perquè amb pesos no n'hi ha prou.)

Dijkstra manté per a cada parada una distància provisional (la millor trobada fins al moment, ∞ si cap) i aplica aquest bucle voraç, pur 03-02:

D'entre les parades encara no consolidades, pren la de menor distància provisional, declara-la definitiva, i relaxa les seves arestes: per a cada veïna, comprova si passar per la parada acabada de consolidar millora la seva provisional.

La "relaxació" és l'operació elemental: si dist[parada] + minuts(parada, veina) < dist[veina], hem trobat una drecera i actualitzem.

Per què aquesta tria voraç no s'equivoca mai? L'argument — cosí de l'argument d'intercanvi de 03-02 — es recolza en una única hipòtesi: cap pes no és negatiu. Sigui p la parada no consolidada amb menor provisional d. Podria existir un camí cap a p més curt que d, encara no descobert? Aquest camí sortiria de la zona consolidada en algun punt i travessaria alguna altra parada no consolidada q abans d'arribar a p. Però només arribar a q ja costa almenys la seva provisional, que és ≥ d (p era la mínima!), i des de q fins a p els trams restants sumen ≥ 0 (aquí entra la hipòtesi). Total: ≥ d. Cap tomb no pot batre d, així que consolidar p amb d és segur — per sempre. És un greedy amb la propietat que a recorregut_supervisor li faltava: cada decisió local ve amb una garantia global demostrada.

Cua de prioritat i heap, en quatre línies. Una cua de prioritat és una estructura que permet inserir elements amb una prioritat i extreure'n sempre el de prioritat mínima. La seva implementació estàndard és el heap binari: un arbre gairebé complet guardat en una llista on cada node és ≤ que els seus fills, de manera que el mínim viu sempre a l'arrel (posició 0). Inserir (heappush) i extreure el mínim (heappop) costen O(log n) — l'element "sura" o "s'enfonsa" al llarg dels ~log₂ n nivells de l'arbre, el mateix recompte de meitats de 04-01. A Python ho dona fet el mòdul heapq, que opera sobre llistes normals; amb tuples (prioritat, dada) compara primer la prioritat.

Per a què el volem? El pas voraç exigeix localitzar "la parada pendent amb menor provisional" moltes vegades. Cercar-la amb un recorregut lineal costaria O(V) cada vegada; el heap la serveix en O(log V).

Tres decisions de disseny que convé entendre:

• Entrades obsoletes. Quan la provisional d'una parada millora, no editem la seva entrada antiga al heap (els heaps no ho suporten amb gràcia): n'afegim una altra amb la distància nova. La nova, en ser menor, sortirà abans; quan més tard aflori la vella, l'if parada in consolidades: continue la rebutja. És la tècnica de l'eliminació mandrosa: més simple i a la pràctica igual d'eficient.
• dist comença en infinit (float("inf")): "encara no conec cap camí". L'infinit de coma flotant compara correctament amb qualsevol suma de minuts i evita tractar els "sense descobrir" com a cas especial.
• previa apunta, per a cada parada, des d'on se la va assolir per darrera vegada amb millora — la molla de pa que a l'apartat 7 ens retornarà el camí complet, no només el seu cost.

Executem dijkstra(xarxa, "Plaça Major"). Abreugem: PM, EN, HC, PR, UNI. Cada fila és una volta del while que consolida una parada:

Resultat: des de la Plaça Major es triga 0 (PM), 4 (EN), 9 (HC), 2 (PR) i 5 (UNI) minuts com a mínim. La traça exhibeix els dos comportaments característics:

• L'ordre de consolidació (PM, PR, EN, UNI, HC) és per distància creixent — el front voraç s'expandeix com una ona des de l'origen.
• El pas 3 mostra una relaxació que corregeix: HC havia estat descobert via PR (10 min) però la ruta per EN el millora a 9. La provisional era això, provisional; només en consolidar-se (pas 5) esdevé veritat definitiva. I el pas 6 mostra l'entrada obsoleta (10, HC) morint en silenci.

dist respon "quant"; l'usuari vol "per on". La resposta és a previa, que després de l'execució val:

És la mateixa jugada que la reconstrucció de la motxilla a 03-03: durant l'algorisme no guardem els camins (serien molts i llargs), guardem una molla per parada — qui la va assolir per darrera vegada amb millora — i al final recorrem les molles cap enrere:

Fixa't en l'elegància estructural: els punters previa formen un arbre de camins mínims amb arrel a l'origen — un sol diccionari codifica el millor camí a totes les parades alhora.

Temps. Comptem amb les eines de 02-01, sent V les parades i E els trams:

• Cada parada es consolida una sola vegada, i en consolidar-se relaxa les seves arestes; cada aresta es relaxa per tant O(1) vegades per extrem → O(E) relaxacions en total.
• Cada relaxació que millora fa un heappush d'O(log·mida del heap). El heap conté com a màxim O(E) entrades (per les obsoletes), i log E ≤ log V² = 2·log V — constant fora (01-03) —, així que cada operació de heap és O(log V).
• Extraccions: O(V + E) heappop, també a O(log V).

Total: O((V + E) · log V). Per a la xarxa real de RutaBus — dispersa: cada parada connecta amb 2-4 veïnes, E ≈ 2V — això és gairebé lineal: amb 10.000 parades, de l'ordre de 4·10⁵ operacions de heap. L'alternativa sense heap (cercar el mínim amb un escombratge lineal) costaria O(V²) — 10⁸ —, que només compensa en grafs molt densos.

Espai: O(V + E) — els diccionaris dist/previa i el heap. Auxiliar lineal, sense ensurts.

La criptonita: pesos negatius. Tota la demostració de l'apartat 3 penjava de "els trams restants sumen ≥ 0". Si un pes pot ser negatiu — imagina un tram bonificat on el bus recupera 4 minuts d'horari — l'argument s'ensorra, i amb ell l'algorisme:

Dijkstra des d'A consolida B amb distància 3 (és la mínima provisional: 3 < 5) i la declara intocable. Però el camí A→C→B costa 5 + (−4) = 1. La consolidació voraç — "res no pot millorar el mínim actual" — era mentida: un tomb aparentment car amagava un descompte. Amb minuts de trajecte això no passa (el temps no recula), però sí tan bon punt els pesos modelen costos amb reemborsaments, diferències o saldos. Per a aquests grafs calen algorismes que no consolidin tan alegrement — i un d'ells, que a més respon a totes-les-parades-contra-totes d'una tacada, és exactament la propera lliçó: Floyd-Warshall.

• Usar-lo amb pesos negatius: no avisa, no falla — retorna distàncies incorrectes amb tota la seguretat en si mateix. Si els teus pesos poden ser negatius, Dijkstra queda descartat d'entrada (apartat 8).
• Oblidar el descart d'obsoletes (if parada in consolidades: continue): l'algorisme reprocessa parades amb distàncies velles; en grafs amb molts cicles pot donar resultats correctes per casualitat però disparar el cost, o corrompre previa. Les entrades duplicades al heap són disseny, el descart n'és l'altra meitat.
• Posar la tupla del heap al revés ((parada, distancia)): heapq compara el primer camp — ordenaries alfabèticament per nom de parada, i el "greedy" consolidaria l'Estació Nord abans que el Parc del Riu sense mirar minuts. Prioritat SEMPRE primer.
• Confondre "descoberta" amb "consolidada": la provisional d'una parada pot millorar diverses vegades (HC: ∞ → 10 → 9) mentre no estigui consolidada. Tractar la primera provisional com a definitiva és reinventar l'error dels pesos negatius sense necessitar-los.
• Consell: per depurar, imprimeix a cada volta la parada consolidada i la seva distància. Han de sortir en ordre no decreixent; si veus una reculada, tens pesos negatius o un bug — aquesta monotonia és la signatura de l'algorisme.

Afegeix la parada "Terminal Sud" connectada amb "Universitat" (7 min) i amb "Hospital Central" (1 min). Traça dijkstra(xarxa, "Plaça Major") amb la taula de l'apartat 6: ordre de consolidació, distàncies finals i previa. En quin pas millora Terminal Sud la seva provisional?

RutaBus vol el camí més curt entre dues parades concretes (origen → destí), no a totes. Modifica dijkstra perquè pugui parar abans: en quin moment exacte és segur retornar la resposta per a desti, i per què? (La justificació és el cor de la lliçó.)

Un becari proposa arreglar els pesos negatius així: "sumo a tots els trams una constant K prou gran perquè cap no quedi negatiu, executo Dijkstra i llestos". Troba la fallada amb aquest contraexemple: A→B directe (pes 1) contra A→C→B (pesos −1 i 1), amb K = 2. Quin camí és realment el més curt i quin tria el Dijkstra "arreglat"?

Solució 1

Amb TS connectat a UNI (7) i HC (1):

Terminal Sud millora al pas 5: descoberta via Universitat (12), corregida via Hospital Central (10). previa["Terminal Sud"] = "Hospital Central", i el camí és PM → EN → HC → TS (4+5+1 = 10). Fixa-t'hi: el veí "car" (HC a 9 min) va resultar millor porta que el "barat" (UNI a 5) — per això no es pot consolidar TS fins que li arriba el torn.

Solució 2

Es pot retornar dist[desti] en el moment en què desti es consolida (surt del heap i passa el filtre d'obsoletes):

Justificació: la consolidació és exactament la garantia que aquesta distància ja no pot millorar (argument de l'apartat 3, vàlid perquè els pesos són ≥ 0). Aturar-se abans — per exemple, la primera vegada que desti rep una provisional — seria incorrecte: HC va rebre 10 abans que 9 a la nostra traça. En el millor cas (destí proper) l'estalvi és enorme; en el pitjor (destí llunyà), es consolida tot igualment — millor/pitjor cas, 02-03.

Solució 3

Pesos reals: A→B = 1; A→C→B = −1 + 1 = 0 ← el més curt. Amb K = 2: A→B = 3; A→C→B = 1 + 3 = 4 → el Dijkstra "arreglat" tria A→B. La fallada: la constant K es cobra una vegada per tram, així que penalitza més els camins amb més trams — distorsiona la comparació entre camins de longitud diferent. Sumar K no trasllada el problema, el canvia per un altre. Els pesos negatius requereixen algorismes pensats per a ells, no maquillatge; Floyd-Warshall (propera lliçó) n'és un.

Dijkstra compleix el que es va prometre a 03-02: un greedy amb demostració. Mantenint distàncies provisionals i consolidant sempre la parada pendent més propera — amb la garantia, vàlida només amb pesos no negatius, que cap tomb no la pot millorar — calcula els camins mínims des d'un origen en O((V+E) log V) gràcies a la cua de prioritat de heapq, i el diccionari de predecessores reconstrueix els itineraris igual que reconstruíem la motxilla a 03-03. La traça des de la Plaça Major ens va ensenyar la seva signatura (consolidació en ordre de distància creixent, provisionals que es corregeixen pel camí) i el contraexemple final ens va ensenyar la seva frontera: un sol pes negatiu i la voracitat torna a ser el pecat que era a canvi_greedy. Però a RutaBus li queda una petició que Dijkstra només resol a força bruta: la web vol la matriu completa de temps entre totes les parades. Executem Dijkstra V vegades, o hi ha res de millor? La resposta és l'algorisme que vam anunciar a 03-03 com "programació dinàmica sobre grafs", que a més digereix pesos negatius sense parpellejar: Floyd-Warshall.