Perché studiare l’algoritmo di Dijkstra

P

“Si è uno studente finché si ha ancora qualcosa da imparare, ovvero per tutta la vita.”

(Henry L. Doherty)

C’è qualcosa che hanno in comune le persone che scelgono di studiare informatica all’università e quelle che invece imparano sul campo. Qualcosa in comune al di là dell’inclinazione all’imprecazione facile e una grave tendenza all’occhiaia.

È quella domanda, che ti tormenta sia che tu stia preparando un esame sia che tu voglia darti basi più solide per aiutarti nel lavoro.

Cosa vale davvero la pena studiare?

Ci sono argomenti che servono per creare la “forma mentis”, figura mitologica di cui tanto si sente parlare, soprattutto quando ti stanno consigliando di iscriverti all’università. Ci sono argomenti che servono per dare le basi, quelle che ti serviranno per andare poi a fondo in un certo campo di studi. Ci sono argomenti che magari a te non servono, ma a chi ha scelto una branca diversa dalla tua sì. E poi, diciamo la verità, ci sono anche argomenti che servono solo ed esclusivamente a passare un esame, e dopo saranno messi nel dimenticatoio.

In un mondo ideale una persona avrebbe tempo per studiare tutto il materiale con il tempo che serve. Nella realtà, essere efficaci significa anche saper scegliere a cosa dare la priorità, a seconda della propria situazione personale, quindi la domanda è più che legittima.

Uno degli argomenti più meritevoli è proprio l’algoritmo di Dijkstra (/ˈdɛikstra/), di larghissimo uso e al cuore di altri algoritmi molto più complessi. Vediamo perché.

Cos’è l’algoritmo di Dijkstra

Pensiamo al movimento di un fulmine che si dirama: non lo fa a caso, ma cercando il percorso a minor resistenza che porti fino al suolo.

L’algoritmo di Dijkstra (pubblicato nel 1956) ha lo scopo di trovare il percorso più breve tra nodi di un grafo. Ne esistono diverse versioni, può essere applicato per trovare il percorso più breve tra un nodo e tutti gli altri o un solo nodo destinazione. Qui vediamo una simulazione che utilizza una coda ordinata secondo valori di priorità per rendere l’esecuzione più veloce, accorgimento ideato nel 1984 (28 anni dopo la “nascita” dell’algoritmo originario) da Fredman e Tarjan.

(Simulazione da visualgo.net)

A cosa serve – protocolli di routing

L’algoritmo di Dijkstra ha un grande vantaggio: è “cieco” nel senso che, per utilizzarlo, non occorre avere alcuna informazione a disposizione. Non usa, inoltre, alcuna euristica: è quindi garantito che il cammino che troverà sarà sempre il minimo.

Questo algoritmo è alla base, per esempio, dei protocolli di routing link state OSPF e IS-IS.

Con il protocollo OSPF i router hanno bisogno di conoscere approfonditamente la rete su cui operano. Avendola esplorata grazie all’algoritmo di Dijkstra, essi sono in grado di gestire casi in cui ci sono cammini con costi molto differenti verso la stessa destinazione.

Il protocollo IS-IS, che procede in modo simile, fa sì che i router inondino la rete con informazioni link state. Ogni router accresce le informazioni ricevute aggiungendovi le proprie e si costruisce così un database di percorsi possibili – e fa tutto questo utilizzando proprio Dijkstra per calcolare quali sono i migliori cammini.

A cosa serve – altri esempi

Ma pensiamo anche a un gioco tipo GTA. In GTA IV la mappa corrisponde a 64 file nodi, e ognuno di questi rappresenta un quadrato da 750×750, dall’angolo sud-ovest (-3000.0, -3000.0) all’angolo nord-est (3000.0, 3000.0). Grazie all’algoritmo di Dijkstra si potrebbe, per esempio, trovare facilmente il percorso più breve tra due punti – mettendo sotto con la macchina il minor numero possibile di persone mentre si ascolta April in Paris alla radio.

Google Maps e simili? È possibile che anche loro usino una versione di Dijkstra, al cuore di un sistema molto più complesso. Il processo effettivo sviluppato da Google non è stato pubblicato (proprio perché molto redditizio), ma si può provare a immaginare come funzioni a grandi linee. Se consideriamo le strade come gli archi di un grafo, gli incroci sarebbero i nodi. Il peso degli archi (quanto mi converrebbe fare una strada piuttosto che un’altra) sarebbe quindi determinato dalla lunghezza della strada, dalla durata dei semafori, dal numero di corsie, dal traffico effettivo e/o stimato. La più grande difficoltà a questo punto è avere abbastanza dati. Ma, visto che Google Maps traccia gli spostamenti di quasi tutti i suoi utenti mobile, e dato che vari progetti Google hanno mappato vastissime aree, questo è diventato un problema relativo.

È possibile utilizzare l’algoritmo anche nell’analisi di immagine mediche. La struttura studiata, infatti, può essere visualizzata come un grafo, dove i diversi livelli di grigio, ovvero la profondità nel mondo reale rappresentano diversi pesi degli archi del grafo. La quantità di pixel tra un nodo e l’altro fornisce le informazioni sulla distanza tra nodi.

Infine, qualcuno online racconta di colloqui, soprattutto con compagnie di social network quali Facebook, in cui gli/le è capitato che l’esaminatore desse un problema da risolvere applicando l’algoritmo di Dijkstra. Del resto, i social network sono costituiti appunto di reti, rese visivamente tramite grafi, quindi la domanda, per quando possa essere inusuale, non è fuori luogo.

Complessità

Proviamo a pensare di non conoscere alcun algoritmo per trovare un cammino minimo.

Procedendo meccanicamente posso analizzare un grafo nel modo seguente. Se dal nodo sorgente partono tre rami avrò tre possibili cammini diversi. Se ognuno di questi tre rami conduce a un nodo dal quale partono altri tre nodi, ogni nodo mi darà altri tre cammini possibili per ciascuna delle tre possibilità. Ho quindi già da esplorare 33 cammini possibili, segnandomi man mano quanto è costato ognuno di essi. E poi ci sono altre variabili da considerare: se i vari cammini possibili s’incrociano tra di loro? Se c’è un ciclo? Quanti tentativi dovrò fare, sommando di peso in peso, prima di arrivare alla destinazione avendo determinato il cammino minimo?

È chiaro subito che, dovendo risolvere un problema come questo, un approccio brute force non è valido.

L’algoritmo originale ideato da Dijkstra per risolvere questo problema ha una complessità di O(|V2|), dove V è il numero di vertici, e procede così:

P[1...n] vettore di padri inizializzati a zero
Dist[1...n] vettore delle distanze inizializzato a +∞
P[a] = a
Dist[a] = 0
A = V

while A ≠ ∅
sia u il nodo in A per cui Dist[u] è minimo
A = A – {u}
for ogni v ∈ adj(u)
		if Dist[u] + p(u,v) < Dist[v]
			P[v] = u
			Dist[v] = Dist[u] + p(u,v)

A è l’insieme di tutti i vertici in un grafo. Finché questo insieme non è vuoto, cerca il nodo più vicino al nodo sorgente, u. Togli questo nodo u dall’insieme A. Per ogni nodo v adiacente a u, se la distanza di u dalla sorgente sommata al peso dell’arco da u a v è minore della distanza di v dalla sorgente, allora u è il padre di v, e la distanza di v dal nodo sorgente va aggiornata, diventando la distanza di u dal nodo sorgente sommata al peso dell’arco da u a v.

Svantaggi e soluzioni

Tuttavia, conviene usare la versione originale dell’algoritmo solo quando il grafo è denso.

Una versione alternativa prevede di appoggiarsi a un heap. In questo caso la complessità è di O((|E| + |V|) log|V|), dove V è il numero di nodi (vertices) ed E il numero di archi (edges).

P[1...n] vettore di padri inizializzati a zero
Dist[1...n] vettore delle distanze inizializzato a +∞
P[a] = a
Dist[a] = 0
H = heap H con V, dove le priorità sono i valori di Dist

while H ≠ ∅
u = il nodo con valore minimo nell’heap H, che viene estratto da esso
for ogni v ∈ adj(u)
		if Dist[u] + p(u,v) < Dist[v]
			P[v] = u
			Dist[v] = Dist[u] + p(u,v)
			decrementa in H la chiave di v a Dist[v]

Dijkstra ha però un limite più grande: non funziona se gli archi hanno peso negativo. In questo caso si ricorre a un altro algoritmo, il Bellman-Ford (1955).

Dist[1...n] vettore delle distanze inizializzato a +∞
P[1...n] vettore di padri inizializzati a zero
P[a] = a
Dist[a] = 0
Vert = numero di nodi nel grafo

for i da 1 a Vert-1
	for ogni arco(u,v)
		if Dist[v] > Dist[u] + p(u,v)
			Dist[v] = Dist[u] + p(u,v)
			P[v] = u

for ogni arco(u,v)
	if Dist[v] > Dist[u] + p(u,v)
		il grafo contiene un ciclo di peso negativo

Oltretutto, se esiste un ciclo formato da archi di peso negativo, un cammino passando per questo ciclo può ridurre il suo peso all’infinito: l’algoritmo di Bellman-Ford si accorge anche di questo – anche se non è in grado di gestirlo, ma solo di segnalarlo.

Altri algoritmi

Ci sono poi altri algoritmi che risolvono lo stesso problema.

A* è un algoritmo che cerca tra tutti i cammini possibili la soluzione che costa di meno. Comincia considerando per primi quelli che sembrano costare di meno, almeno all’apparenza. Partendo dal nodo sorgente, costruisce un albero di cammini che partono da esso, andando avanti un passo per volta. Alla fine, uno solo dei cammini iniziati arriverà al nodo destinazione. In generale è un algoritmo molto potente e accurato, ma la sua complessità dipenderà dall’euristica su cui si basa. Di fatto è un’estensione dell’algoritmo di Dijkstra.

L’algoritmo di Floyd–Warshall confronta tutti i possibili cammini tra ogni coppia di nodi. Parte da una stima su quale sia il cammino migliore possibile tra due nodi e migliora man mano questa ipotesi, fino ad aver trovato la migliore possibile. Ha complessità Θ(|V|)3. Per restituire il risultato c’è un ulteriore costo di Θ(|E|) per ogni nodo. Si utilizza su grafi pesati con pesi negativi o positivi, ma privi di cicli.

L’algoritmo di Johnson aggiunge un nuovo nodo al grafo, connettendo archi di peso zero a tutti gli altri nodi. Poi usa l’algoritmo di Bellman-Ford, quindi nota anche l’eventuale presenza di cicli negativi. Infine ripesa gli archi sulla base delle informazioni raccolte dal Bellman-Ford, toglie il nodo aggiunto all’inizio, e fa partire l’algoritmo di Dijkstra per trovare il cammino più breve. Ha complessità O(|V|2 log|V| + |V||E|). Si usa su grafi diretti, pesati, e non densi. Funziona anche su pesi negativi, ma non devono esserci cicli negativi.

Conclusione

Dijkstra, inventore anche del concetto informatico di semaforo, attribuiva alla madre Brecthje Cornelia Klujiver, una brillante matematica, la propria capacità di trovare soluzioni eleganti a problemi complessi (modestamente). In effetti, è considerato un pioniere dell’informatica e i suoi algoritmi si studieranno ancora per anni a venire.

Sull’algoritmo di Dijkstra si è costruito moltissimo. In un certo senso, si può dire che sia stato “scoperto molte volte”, come dimostrano le sue diverse varianti, tra le quali sta al programmatore scegliere di volta in volta a seconda del contesto.

Avere una chiara idea di cos’è e come funzioni, quindi, è fondamentale in alcuni campi, e molto utile a prescindere. È uno dei mattoni che compongono la base di conoscenze che dovrebbero essere bagaglio di chiunque si addentri nel campo della programmazione.

Vale la pena spenderci un po’ di tempo, sia che si stia studiando, sia che si stia lavorando.
O, com’è più spesso il caso con gli informatici, entrambe le cose contemporaneamente.

A proposito di me

Flavia Bonanni

Ha imparato a scrivere a 4 anni, anche se il suo linguaggio inintelligibile era incomprensibile ai più. Per la prima comunione ha chiesto in regalo un computer, e da li è cominciata una love story che non ha mai subito battute d’arresto. Attualmente lavora nella sede centrale di una grande no profit. Di giorno si occupa, tra le altre cose, di amministrazione economica, graphic design, sviluppo siti web e presenza sui social media. Di notte studia informatica e si dedica a progetti freelance.
Si narra che talvolta dorma.

Di Flavia Bonanni

Gli articoli più letti

Articoli recenti

Commenti recenti