Google Maps e la teoria dei grafi

Google Maps si basa su un algoritmo molto semplice ma incredibilmente efficace: l’algoritmo di Dijkstra. Esso prende il nome dal suo inventore, Edsger Dijkstra, uno dei fondatori pionieri dell’informatica moderna.

Una passeggiata destinata a cambiare la storia. Era una mattina del 1956 e Dijkstra, che allora lavorava come programmatore al Centrum Wiskunde & Informatica (CWI) di Amsterdam, stava passeggiando con la sua fidanzata per fare un po’ di shopping. Quando stanchi di camminare si sedettero a un tavolino di un caffè, lo scienziato olandese ebbe un’illuminazione: in soli 20 minuti, davanti a una tazza di caffè, progettò l’algoritmo che lo avrebbe fatto entrare nella storia dell’informatica.

Per capire come funziona dobbiamo introdurre il concetto di grafo. Un grafo, come quello rappresentato nella figura, è una struttura formata da nodi, rappresentati dai pallini, e di archi, delle linee che connettono i nodi. Seppur semplice, questo modello può essere utilizzato per descrivere moltissimi problemi. Per esempio, i nodi possono rappresentare le persone e gli archi collegano le persone che si conoscono; in anatomia i nodi possono rappresentare gli organi e gli archi i vasi sanguigni che li connettono, in astronomia le stelle sono dei nodi che uniti dagli archi formano le costellazioni. Nel nostro caso, invece, gli archi rappresentano le strade, mentre i nodi sono gli incroci, ossia tutti i punti in cui è possibile scegliere quale strada prendere.

Una mappa diventa un grafo: le strade sono archi (le linee nere), mentre gli incroci sono nodi (i cerchi bianchi)

Gli archi non sono tutti uguali. Quando dobbiamo scegliere tra due possibili strade teniamo conto di quella che ci fa arrivare prima. I fattori che entrano in gioco sono molteplici: la velocità massima, la dimensione della strada, la presenza di semafori, il traffico e così via. Possiamo riassumerli tutti in un unico valore, il tempo (stimato) di percorrenza di quel tratto. Questa informazione viene integrata nel nostro grafo tramite dei pesi, ossia dei valori attribuiti ad ogni arco. Di conseguenza, se sull’arco che collega il nodo X e il nodo Y c’è scritto un “4”, questo indica che per andare dall’incrocio X all’incrocio Y stimiamo di impiegare 4 minuti.

Cosa fa l’algoritmo di Dijkstra? Dato un grafo pesato, un punto di partenza e un punto di arrivo all’interno del grafo stesso, l’algoritmo trova il “cammino minimo” che collega i due punti, ossia la sequenza di archi che minimizza la somma dei pesi e che quindi, nel caso di Maps minimizza il tempo stimato di percorrenza.

Uno sguardo più approfondito. Per funzionare correttamente l’algoritmo tiene un “costo” associato a ogni nodo, che rappresenta il valore del cammino minimo per arrivare a ciascun nodo. Prima di iniziare, ai nodi viene assegnato “a tavolino” un costo infinitamente alto, che indica che non è ancora stata trovata una strada per raggiungerlo. A tutti tranne al nodo di partenza, che viene impostato a costo zero (d’altronde arrivare al nodo di partenza dal nodo di partenza non ha costo!). Inoltre, tiene una lista di tutti i nodi che sono ancora da visitare, che in partenza comprende tutti i nodi della rete. L’algoritmo ripete sempre gli stessi passaggi. Come prima cosa estrae, dalla lista dei nodi da visitare, il nodo con il costo più basso. Per ogni nodo non ancora visitato della rete raggiungibile dal nodo esaminato, l’algoritmo valuta quanto costa raggiungere tale nodo. Se il costo è minore allora viene aggiornato, altrimenti viene lasciato invariato, visto che esiste una strada più conveniente. Il nodo appena esaminato viene segnato come visitato e si ricomincia, finché il nodo da visitare non risulta la destinazione.
Questo video mostra un esempio completo del suo funzionamento.

L’algoritmo di Dijkstra trova sempre il percorso più veloce. È stato dimostrato matematicamente che Dijkstra trova sempre il percorso più breve, a patto che esista almeno una strada percorribile. Questo fatto talvolta gioca contro di noi: spesso, infatti, il navigatore per risparmiare qualche manciata di secondi ci manda su strade “alternative” contro il comune buon senso, e che non ci saremmo mai sognati di fare. D’altro lato però è estremamente versatile, infatti è in grado di trovare sempre il percorso più veloce. Inoltre, può tenere conto di informazioni aggiuntive come le informazioni sul traffico o la presenza di congestionamenti, semplicemente andando a modificare i pesi sul grafo. Ma come fa Google a sapere informazioni sul traffico? Utilizza i dati raccolti dagli altri utenti, ma questa è un’altra storia…