Dall’abc al SEO: Scopriamo insieme l’Algoritmo di Dijkstra attraverso un esempio pratico!

Introduzione al problema del cammino minimo

Il problema del percorso più breve è un problema classico nella teoria dei grafi, che consiste nel trovare il percorso più breve tra due vertici di un grafo pesato. Un grafico è una struttura matematica composta da nodi (o vertici) collegati da bordi (o collegamenti). I grafici possono essere orientati o meno, a seconda che gli spigoli abbiano o meno una direzione. In un grafico ponderato, ogni bordo ha un valore chiamato peso, che in genere rappresenta la distanza o il costo associato a quella connessione.

Algoritmo di Dijkstra

L’algoritmo di Dijkstra, inventato da Edsger W. Dijkstra nel 1956, è una delle soluzioni più conosciute a questo problema. Questo è un algoritmo goloso che costruisce progressivamente un sottografo contenente le distanze minime da un vertice sorgente a tutti gli altri vertici del grafico.

Per capire come funziona questo algoritmo, utilizzeremo un esempio concreto che coinvolge le città come nodi e le distanze stradali come pesi.

Esempio pratico: rete stradale tra città

Immaginiamo di avere la seguente rete stradale:

• Città A: punto di origine
• Città B: distanza 10 km da A
• Città C: distanza 20 km dalla A, 5 km dalla B
• Città D: distanza 30 km da A, 15 km da B, 10 km da C

Passi dell’algoritmo di Dijkstra

L’algoritmo di Dijkstra segue i seguenti passaggi:

1. Inizializzazione: ad ogni vertice viene assegnato un valore provvisorio corrispondente alla distanza tra questo vertice e il punto di origine. Per il punto di origine, questo valore è zero. Per tutti gli altri vertici è infinito.
2. Selezione del nodo non visitato con il valore provvisorio più piccolo (scegliamo inizialmente il punto di origine).
3. Per ogni vicino del nodo selezionato:
   1. Calcola la nuova distanza passante per il nodo selezionato.
   2. Aggiorna il valore provvisorio se questa nuova distanza è inferiore a quella vecchia.
4. Contrassegna il nodo selezionato come visitato.
5. Ripetere i passaggi da 2 a 4 finché non vengono visitati tutti i nodi o viene raggiunta la destinazione desiderata.

Illustrazione dei passaggi con il nostro esempio concreto

Nel nostro esempio, stiamo cercando il percorso più breve tra la città A (punto di origine) e la città D (destinazione). Ecco come funziona l’algoritmo di Dijkstra:

Passaggio 1: inizializzazione