L’algoritmo di Dijkstra è uno degli algoritmi più importanti e utilizzati in ambito informatico per risolvere problemi di cammino minimo in un grafo pesato. L’algoritmo, inventato da Edsger Dijkstra nel 1956, trova il cammino più breve tra due nodi di un grafo pesato con pesi non negativi.
In sostanza, l’algoritmo di Dijkstra funziona in modo simile all’algoritmo di Breadth-First Search (BFS), con la differenza che l’algoritmo di Dijkstra utilizza una coda di priorità invece di una coda standard. La coda di priorità viene utilizzata per selezionare il nodo con il costo minimo per l’aggiunta alla lista di nodi visitati.
(Scarica le slide animate dell’algoritmo di Dijkstra).
L’algoritmo inizia dal nodo sorgente e visita tutti i nodi raggiungibili, aggiornando costantemente i costi dei cammini più brevi man mano che visita i nodi. In particolare, ogni volta che viene visitato un nodo, l’algoritmo aggiorna i costi dei cammini verso i suoi vicini, se il costo del cammino che passa attraverso il nodo visitato è minore del costo del cammino più breve trovato fino ad ora.
L’algoritmo continua fino a quando non ha visitato tutti i nodi raggiungibili dal nodo sorgente, e termina quando il nodo destinazione è stato visitato o quando tutti i nodi raggiungibili sono stati visitati.
L’algoritmo di Dijkstra è particolarmente utile per problemi di routing in reti di computer e per la progettazione di algoritmi di ricerca del percorso più breve in applicazioni come mappe e GPS.
Un esempio di implementazione dell’algoritmo di Dijkstra in Python è il seguente:
In questo codice, graph rappresenta il grafo pesato rappresentato come un dizionario di dizionari, dove ogni nodo è una chiave del dizionario principale e i valori sono un altro dizionario che rappresenta i vicini del nodo e il peso dell’arco che li collega.
Il nodo di partenza viene passato come argomento alla funzione dijkstra, che restituisce un dizionario contenente i costi minimi dei cammini per ogni nodo raggiungibile dal nodo di partenza.
In sintesi, l’algoritmo di Dijkstra è un algoritmo fondamentale per la risoluzione di problemi di cammino minimo in un grafo pesato. La sua implementazione è relativamente semplice, ma può essere utilizzata per risolvere problemi molto complessi.