Come si fa a calcolare il miglior percorso da punto A a B: l’algoritmo dei cammini minimi di Dijkstra

Determinare il percorso più veloce tra due punti è un problema centrale in molti ambiti applicativi: dalla navigazione satellitare alla gestione delle reti, dalla logistica ai videogiochi, sino alle mappe online che consultiamo abitualmente. Alla base di queste applicazioni si trovano modelli matematici, chiamati grafi, e algoritmi capaci di individuare il percorso ottimale. Tra questi, uno dei più importanti è l’algoritmo di Dijkstra, che consente di calcolare in modo efficiente il cammino minimo tra un punto di partenza e una destinazione. Su questo principio si basano gran parte dei sistemi di navigazione che utilizziamo ogni giorno.

Il problema del percorso ottimale

Per rappresentare il problema si utilizza un ente matematico chiamato grafo, costituito da nodi (o vertici), che rappresentano punti significativi come incroci, città o dispositivi, e da archi, che descrivono invece i collegamenti tra tali nodi. A ogni arco è associato un peso; spesso si tende a interpretare questo peso come il tempo di percorrenza, ma si tratta in realtà di un concetto più generale, ossia il costo.

Il peso di un percorso, che è un insieme di archi e nodi, può far riferimento a diverse grandezze:

• Distanza fisica
• Tempo di viaggio
• Consumo di carburante
• Pedaggi o costi economici
• Livello di sicurezza o rischio

Nei problemi reali, questi fattori non agiscono separatamente, ma in modo combinato. Nelle applicazioni teoriche si introduce quindi il concetto di costo generalizzato, ovvero una grandezza sintetica che integra più variabili in un unico parametro. Il costo generalizzato non ha necessariamente un’unità di misura fisica: è una quantità “normalizzata” che consente di confrontare elementi diversi tra loro. In altre parole, si costruisce un indicatore unico che rappresenta il comportamento complessivo del sistema.

Ad esempio, un navigatore può combinare tempo di percorrenza, condizioni di traffico e consumo energetico. Il problema diventa quindi trovare il percorso che minimizza il costo generalizzato totale, non necessariamente il tempo.

Come funziona l’algoritmo di Dijkstra

L’algoritmo di Dijkstra è una procedura che, a partire da un nodo iniziale e identificato un nodo finale, individua il percorso a costo minimo verso gli altri nodi del grafo fino al nodo di arrivo. Si basa su un approccio detto greedy (letteralmente "ingordo") che, a ogni passo, sceglie la soluzione localmente migliore, costruendo progressivamente la soluzione globale. Per capire come funziona, possiamo immaginare lo schema dell'algoritmo suddiviso in quattro fasi logiche:

• Inizializzazione: si assegna un costo pari a zero al punto di partenza, mentre tutti gli altri nodi del grafo vengono inizialmente trattati con costo infinito, poiché non sappiamo ancora come raggiungerli.
• Selezione: tra tutti i nodi non ancora analizzati, si sceglie quello che ha il costo registrato più basso. Questo nodo diventa il nostro punto di riferimento corrente e rappresenta il percorso più conveniente noto fino a quel momento.
• Aggiornamento: si analizzano i nodi direttamente collegati, tramite archi, al nodo corrente. Per ciascuno di essi, si verifica se, passando attraverso il nodo corrente, si ottiene un costo totale minore rispetto a quello registrato in precedenza. Se il nuovo percorso è più economico, si aggiorna il valore del costo e si annota il nodo corrente come "passaggio precedente". Questo servirà, alla fine, a ricostruire a ritroso il percorso ottimale (cioè la soluzione). Una volta completata la verifica, il nodo di riferimento viene marcato come definitivo, in quanto siamo certi che il costo per raggiungerlo non potrà più migliorare.
• Iterazione: si ripetono i passaggi di selezione e aggiornamento finché non si raggiunge la destinazione finale o non si esauriscono i nodi da analizzare.

L’algoritmo può essere immaginato visivamente come un’onda che si propaga a cerchi concentrici a partire dal nodo iniziale. Questa espansione si estende prima verso i nodi a costo minore e, passo dopo passo, mappa l'intera rete. Questo meccanismo garantisce che un nodo venga "fissato" come definitivo solo quando si è matematicamente certi che la strada trovata sia la più efficiente in assoluto.

Tuttavia, questa logica basata sull'espansione progressiva dell'onda svela anche il principale limite teorico dell'algoritmo: la necessità che tutti i costi (i pesi degli archi) siano positivi. Se esistessero costi negativi, un percorso inizialmente più lungo e scartato dall'onda potrebbe rivelarsi improvvisamente più economico in un secondo momento, mandando in crisi l'intero processo di selezione e impedendoci di considerare "definitivo" qualsiasi nodo appena visitato.

Applicazioni, complessità e limiti

L’algoritmo di Dijkstra è una pietra miliare dell’informatica per semplicità e robustezza  ed è ancora oggi ampiamente utilizzato in numerosi ambiti, come sistemi di navigazione (calcolo dei percorsi ottimali su rete stradale con il gps), logistica (ottimizzazione dei percorsi di consegna), reti informatiche e intelligenza artificiale. Le prestazioni dell'algoritmo dipendono dalle strutture dati utilizzate, così che più è semplice la sua implementazione, meno efficiente è l'algoritmo e quindi i suoi tempi risolutivi. Tuttavia,  nonostante i vantaggi, esistono alcune limitazioni. Come detto prima, l'algoritmo non funziona con pesi negativi. Inoltre, può essere oneroso su grafi molto grandi senza ottimizzazioni adeguate e ha il vincolo di necessitare di un'unica sorgente di partenza: per problemi più complessi sono quindi necessarie delle varianti.

non perderti questo articolo

Come fanno gli algoritmi a decidere cosa raccomandarci e sapere cosa ci piace