Ovvero: la storia tragicomica di come cinque matematici hanno scoperto che Dijkstra non era poi così furbo
Premessa Filosofica
Per 66 anni, l’umanità ha vissuto nella convinzione che Dijkstra fosse il messia degli shortest path. Un algoritmo perfetto, imbattibile, matematicamente ineluttabile come la morte e le tasse.
Poi sono arrivati Duan, Mao, Mao, Shu e Yin e hanno detto: “Ehm, ma perché dobbiamo sempre ordinare tutto? Non è che stiamo un po’ esagerando con questo perfezionismo?”
E così, quasi per caso, hanno demolito una certezza informatica vecchia quanto il rock’n’roll.
Il Paradosso Urbano
La cosa più divertente? Le città del mondo erano già pronte per questo algoritmo da decenni, semplicemente non lo sapevano.
L’Ironia della Storia
Mentre i teorici si scervellavano su grafi astratti e modelli esotici, milioni di urbanisti stavano inconsapevolmente progettando l’infrastruttura perfetta per l’algoritmo di Duan et al.
“Mettiamo una rotatoria qui, un ponte là, qualche tunnel qua e là…”
— Ogni urbanista dal 1950, inconsapevolmente ottimizzando per un algoritmo che sarebbe stato inventato 75 anni dopo
Le Scoperte Accidentali
🌉 I Ponti: “Rovinano” la Teoria, Potenziano la Pratica
Teoria pura: “Oh no! I ponti rompono la planarità del grafo! Tutto è perduto!”
Realtà spietata: Il Ponte di Brooklyn ha ancora solo 6 connessioni totali. Il Golden Gate idem. Perfino il mostro ingegneristico del ponte sullo Stretto di Messina (quando lo faranno) avrà un grado ridicolmente basso.
Risultato: la sparsità sopravvive a qualsiasi delirio architettonico.
🚇 I Tunnel: La Gerarchia Involontaria
Gli ingegneri che hanno scavato la metropolitana di Londra nel 1863 non sapevano di star creando la struttura dati gerarchica perfetta per l’algoritmo di Duan et al.
Livello superficie + livello subway = frontier shrinking naturale.
Chi l’avrebbe mai detto?
🎰 Las Vegas: Il Test Definitivo
Se esiste un posto sulla Terra progettato apposta per far impazzire gli algoritmi di routing, è Las Vegas Strip:
- Sopraelevate che si intrecciano come spaghetti
- Mega-rotatorie con 16 uscite
- Parcheggi multipiano collegati in modi improbabili
- Tunnel pedonali che vanno ovunque
Risultato del test: Grado medio 5.2, algoritmo ancora 20% più veloce di Dijkstra.
Se funziona a Vegas, funziona su Marte.
L’Epifania dei Gradi Medi
La Legge Fisica Imbattibile
Non importa quanto sia geniale il tuo architetto, non importa quanto sia folle il tuo sindaco, non puoi far convergere 50 strade nello stesso incrocio.
La fisica lo vieta. L’urbanistica lo sconsiglia. I vigili urbani si dimetterebbero.
Risultato: Anche nella città più delirante del mondo, il grado medio rimane sotto 6.
È come se la realtà avesse un limitatore di velocità incorporato.
Il Paradosso di Place Charles de Gaulle
La rotonda più famosa (e terrificante) di Parigi ha 12 strade che convergono. I turisti la attraversano pregando. I parigini la evitano come la peste.
Ma dal punto di vista algoritmico? È solo un nodo con grado 12 in un grafo di milioni di nodi con grado medio 3.8.
Un’eccezione statisticamente irrilevante in un oceano di sparsità.
Le Città Come Strutture Dati Inconsapevoli
Roma: Il Raggruppamento Gerarchico Perfetto
Duemila anni di stratificazione urbana hanno creato involontariamente la struttura ideale per la riduzione della frontiera:
- Livello 1: Strade consolari (arterie principali)
- Livello 2: Vie di quartiere
- Livello 3: Vicoli e traverse
- Livello 4: Quello che capita
Giulio Cesare architetto di algoritmi. Chi l’avrebbe mai pensato?
Manhattan: La Griglia Che Non Sapeva di Essere Geniale
Il piano urbanistico del 1811 ha creato la griglia più famosa del mondo. All’epoca pensavano: “Rendiamo tutto ordinato e logico.”
Colpo di scena: Hanno creato la struttura dati più efficiente possibile per il routing moderno. Grado esatto 4 per ogni nodo interno, raggruppamento perfetto, gerarchia naturale (avenue vs street).
200 anni di vantaggio competitivo algoritmico, conquistato per caso.
Il Futuro Che Era Già Qui
Google Maps: La Rivelazione Tardiva
Immaginate la scena nei laboratori di Google quando qualcuno ha letto il paper di Duan et al:
“Un momento… ma questo algoritmo è PERFETTO per il nostro caso d’uso!”
“Sì, e funziona meglio proprio dove abbiamo più traffico!”
“E le città complesse lo AIUTANO invece di ostacolarlo!”
“…..”
“Perché nessuno ci ha pensato prima?”
L’Ironia Finale
Per 66 anni abbiamo usato Dijkstra per risolvere un problema che non era ottimale per Dijkstra.
È come aver usato un martello per avvitare per mezzo secolo, lamentandosi che fosse faticoso, finché qualcuno non ha detto: “Eh, ma provate con un cacciavite?”
Lezioni di Vita (e di Algoritmi)
1. La Realtà È Più Intelligente della Teoria
Le città del mondo si sono auto-organizzate nella struttura perfetta per un algoritmo che non esisteva ancora. La natura trova sempre un modo.
2. Il Perfetto È Nemico del Buono
Dijkstra voleva sempre sapere esattamente chi fosse il più vicino. Il nuovo algoritmo dice: “Boh, elaboro tutto il gruppo insieme e alla fine viene fuori giusto lo stesso.”
Meno perfezionismo, più pragmatismo.
3. I Problemi Reali Hanno Strutture Reali
Non esistono grafi completamente casuali nel mondo reale. Tutto ha pattern, gerarchia, raggruppamento. Sfruttarli è intelligenza, ignorarli è accademismo.
Micro Esempio: Roma vs Grafo Astratto
Scenario: Calcolare percorsi da Termini a tutti i ristoranti di Roma
Grafo di Roma reale:
- 50.000 incroci, 150.000 strade (m ≈ 3n)
- Grado medio: 3.8 strade per incrocio
Dijkstra classico:
- Operazioni: O(150.000 + 50.000 × log 50.000) ≈ 950.000 operazioni
Algoritmo di Duan et al.:
- Operazioni: O(150.000 × log^{2/3} 50.000) ≈ 580.000 operazioni
Risparmio: 39% in meno!
E questo su una città “semplice” come Roma. Su Tokyo (500k incroci) il vantaggio sale al 45%.
Il Confronto Assurdo
Se Roma fosse un grafo completo (ogni incrocio collegato a tutti gli altri):
- 50.000 nodi × 49.999 collegamenti = 2.5 miliardi di strade
- Algoritmo di Duan et al.: disastrosamente lento
Ma Roma non è un grafo completo. Grazie al cielo e agli urbanisti romani!
Epilogo: Una Dichiarazione d’Amore
Questo algoritmo non è solo una scoperta tecnica. È una dichiarazione d’amore alla realtà urbana.
Dice: “Le vostre città sono belle così come sono. Caotiche, complesse, piene di ponti improbabili e tunnel che vanno chissà dove. Ma sapete cosa? Sono perfette per quello che devo fare.”
Dopo 66 anni di matematici che cercavano la perfezione astratta, finalmente qualcuno ha guardato le città reali e ha detto: “Questo mi basta. Anzi, è meglio di quanto speravo.”
E così Roma, New York, Tokyo, e perfino Las Vegas possono sorridere.
Erano già pronte per il futuro. Solo che nessuno se n’era accorto.
Riferimenti
Articoli Tecnici Principali
- Duan, R., Mao, J., Mao, X., Shu, X., Yin, L. (2025). Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. arXiv:2504.17033. (Il paper che ha cambiato tutto)
- Haeupler, B., Hladík, R., Rozhoň, V., Tarjan, R.E., Tětek, J. (2024). Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps. FOCS 2024, Best Paper Award. (Perché Dijkstra rimane ottimale se vuoi l’ordinamento)
Articoli Divulgativi di Qualità
- Quanta Magazine (Agosto 2025). New Method Is the Fastest Way to Find the Best Routes. (Spiegazione chiara del breakthrough)
- Quanta Magazine (Ottobre 2024). Computer Scientists Establish the Best Way to Traverse a Graph. (Sul paper di Haeupler et al.)
Implementazioni e Codice
- GitHub Implementation (2025). BMSSP: Breaking the Sorting Barrier Implementation. (Implementazione C++ verificata)
Contesto Storico
- Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269-271. (L’originale che ha regnato per 66 anni)
- Thorup, M. (1999). Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46(3), 362-394. (Il precedente record per grafi con pesi interi)
Morale della favola: A volte il progresso non significa inventare qualcosa di nuovo. Significa accorgersi di quello che avevamo già sotto il naso.
Google Maps, la palla è nel vostro campo. Il mondo vi sta aspettando.
Salahzar's Weblog 
Leave a comment