di Sergio Mauri
L’algoritmo di Dijkstra è un algoritmo utilizzato per trovare il cammino più breve da un nodo di partenza a tutti gli altri nodi in un grafo pesato non negativo. La sua formula si basa su concetti di programmazione dinamica e funziona in questo modo:
Sia G un grafo pesato non negativo, e siano s il nodo di partenza e d(v) la lunghezza attuale del cammino più breve da s a v per ogni nodo v nel grafo.
L’algoritmo di Dijkstra procede nel seguente modo:
- Inizializza d(s)=0 e d(v)=∞ per ogni nodo v≠s.
- Finché ci sono nodi non visitati nel grafo:
- Scegli il nodo u non visitato con la distanza minima, cioè d(u), e contrassegnalo come visitato.
- Per ogni arco (u,v) uscente da u, aggiorna la distanza d(v) se il percorso attraverso u è più breve del percorso attualmente conosciuto. L’aggiornamento avviene tramite l’equazione: d(v)=min(d(v),d(u)+w(u,v)) dove w(u,v) è il peso dell’arco tra u e v.
- Una volta che tutti i nodi raggiungibili sono stati visitati, d(v) contiene la distanza minima da s a ogni nodo v nel grafo.
L’algoritmo di Dijkstra garantisce la correttezza poiché, ad ogni passo, seleziona il nodo con la distanza minima dal nodo di partenza. Questo nodo diventa quindi definitivamente visitato e non verrà mai più rivisitato, garantendo che la distanza minima di quel nodo sia stata determinata correttamente. La complessità temporale dell’algoritmo di Dijkstra dipende dall’implementazione e può variare da O(V^2) a O(E+V log V), dove V è il numero di nodi e E è il numero di archi nel grafo.
