Come arrivare prima: l’algoritmo di Dijkstra

Siete in ritardo.

Come al solito dopotutto. Ma stavolta avete quell’appuntamento con X e non volete assolutamente far attendere il vostro arrivo.

Un pizzico di risentimento vi lacera il fegato mentre vi domandate come fate a ridurvi sempre all’ultimo momento e a ritrovarvi a fare sempre delle corse disperate in giro per la città.

Mentre le lancette sfrecciano ruotando attorno al centro del vostro orologio da polso, vi concentrate su un unico obiettivo: percorrere il percorso più veloce, per risparmiare quanto più tempo possibile.

L’adrenalina in corpo rende il vostro pensiero affilato: per trovare il cammino più veloce non potete dividere il percorso in tanti piccoli pezzettini e trovare il percorso più rapido per ogni piccolo pezzettino per poi metterli tutti insieme.

insomma, dovete attraversare la città da parte a parte e in termini di tempo non conviene prendere le stradine del centro, ma allungare e prendere la tangenziale.

Vi serve cioè quella che si chiama una soluzione globale.

Il mio amico grafo

Il primo passo per risolvere il problema è trovare l’infrastruttura matematica adatta a descrivere il problema.

Nel nostro caso, possiamo ricorrere ai nostri amici GRAFI.

Come ne abbiamo già scritto in passato (ad esempio riguardo il problema dei ponti di Königsberg o ne Il Teorema dei quattro colori), un grafo è un oggetto costituito da dei puntini (chiamati vertici) collegati tra loro attraverso delle linee (chiamate archi), in modo da ridurre all’osso le proprietà davvero importanti di un problema di natura topologica, come in Figura 1.

Nel nostro caso, gli archi sono le strade della città che vogliamo attraversare e i nodi sono gli incroci stradali.
Gli archi sono dotati di un numeretto, che nella nostra astrazione sta a indicare il tempo necessario per percorrere la strada.

Il nostro obiettivo è quindi di trovare il cammino più breve per arrivare da A a B, ovvero scegliere in maniera ordinata degli archi sul grafo che connettano A con B in modo tale che la somma dei numeretti sia la più piccola possibile.

Vi vedo già che state pensando che si riconosce a occhio quale sia il percorso più breve in Figura 1; non si vede a occhio, però, quando il grafo è mooolto più grande e voi vorreste affidarvi al navigatore GPS preferito per trovare la strada con meno traffico.

Manteniamo quindi il nostro esempio facile per capire come funzionano le cose senza farci venire il mal di testa.

L’algoritmo di Dijkstra

L’algoritmo di Dijkstra è stato scoperto dall’informatico olandese Edsger Dijkstra nel’11.956 EU (1956 d.C.) ed è utilizzato per trovare il cammino minimo su un grafo.

Come funziona?

Nella seguente tabella mettiamo in una colonna i vertici, in una il costo (in termini di tempo) per raggiungere un vertice a partire da A, e infine la colonna con il vertice che lo precede nel cammino che lo porta ad avere tale costo.

Iniziamo quindi a mettere 0 nel costo di A e tutti gli altri al momento li mettiamo provvisoriamente di costo “infinito”.

Vertice	Costo	Predecessore
A	0	–
B	∞	–
C	∞	–
D	∞	–

Partiamo da A.
Quali sono i suoi adiacenti? Sono C e D.

Per ognuno dei suoi vertici adiacenti andiamo a calcolare il costo per arrivare a quel vertice passando per A: se questo costo è minore di quello segnato in tabella, aggiorniamo la tabella e mettiamo A nella colonna “Predecessore”.

Il costo di C passando per A è 1, che è più piccolo di “infinito”, quindi la nostra tabella diventerà:

Vertice	Costo	Predecessore
A	0	–
B	∞	–
C	1	A
D	∞	–

Il costo di D passando per A è 3, che è più piccolo di “infinito”, quindi la nostra tabella diventerà:

Vertice	Costo	Predecessore
A	0	–
B	∞	–
C	1	A
D	3	A

Abbiamo esaurito i vertici adiacenti ad A, possiamo quindi considerare finito il lavoro su A, colorarlo di rosso, e spostarci su uno dei suoi vertici adiacenti (non colorati in rosso) e ricominciare da capo.

Come si compila il resto della tabella?

Passiamo a C e per ognuno dei suoi vertici adiacenti  (non colorati di rosso) calcoliamo il costo per arrivarci passando per C (sommando anche il costo di C): se questo costo è minore di quello segnato in tabella, aggiorniamo la tabella e mettiamo C nella colonna “Predecessore”.

Il costo di B passando per C è 1+4=5, che è più piccolo di “infinito”, quindi la nostra tabella diventerà:

Vertice	Costo	Predecessore
A	0	–
B	5	C
C	1	A
D	3	A

Il costo di D passando per C è 1+1=2, che è più piccolo di 3, quindi la nostra tabella diventerà:

Vertice	Costo	Predecessore
A	0	–
B	5	C
C	1	A
D	2	C

Abbiamo finito con C, che abbiamo quindi appena colorato in rosso, e ripetiamo la stessa procedura con D.

L’unico vertice non rosso oltre a D è B; il costo di B passando per D è 2+1=3, che è più piccolo di 5, quindi la nostra tabella diventerà:

Vertice	Costo	Predecessore
A	0	–
B	3	D
C	1	A
D	2	C

Abbiamo finito perché l’ultimo vertice non rosso è proprio il nostro punto di arrivo! La nostra tabella dell’algoritmo di Dijkstra è completa! 

La risposta

Molto bella la tabella, ma a che serve? Cosa c’entra questo con il tragitto più rapido per andare da A a B?

Ecco dove si manifesta la bellezza dell’algoritmo di Dijkstra:

Basta leggere la tabella a partire dal nostro punto di arrivo B e seguire chi sono i vertici precedenti. Il cammino più breve è nelle vostre mani! 

Il predecessore di B è D. Quello di D è C. Ed infine, il predecessore di C è A.

Il nostro cammino minimo è quindi A->C->D->B come disegnato in rosso in Figura 2.

 

CONGRATULAZIONI! Anche questa volta il vostro ritardo non è abissale!

 

Fonti

[1] -: Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), (pp. 269–271). doi: 10.1007/BF01386390

[2] -:  Johnson, D. B. (1973). A note on Dijkstra’s shortest path algorithm. Journal of the ACM (JACM), 20(3), 385-388. doi: 10.1145/321765.321768