Qual è il percorso più breve per andare da Rotterdam a Groninga? Si tratta di utilizzare l’algoritmo del percorso più breve, che ho progettato in circa 20 minuti. Una mattina stavo facendo shopping ad Amsterdam con la mia giovane fidanzata e, stanchi, ci siamo seduti sulla terrazza di un bar per bere una tazza di caffè e stavo pensando se potevo farlo e poi ho progettato l’algoritmo per il percorso più breve. Come ho detto, fu un’invenzione di 20 minuti. In realtà, fu pubblicato nel 1959, tre anni dopo. La pubblicazione è ancora molto bella. Uno dei motivi per cui è così bello è che l’ho progettato senza carta e penna. Senza carta e penna si è quasi costretti a evitare tutte le complessità evitabili. Alla fine quell’algoritmo è diventato, con mio grande stupore, una delle pietre miliari della mia fama. (Edsger W. Dijkstra)
L’algoritmo di Dijkstra è utilizzato per trovare il percorso più breve da un nodo di partenza a tutti gli altri nodi in un grafo con pesi sugli archi non negativi. Questo procedimento è efficace su grafi non direzionati e direzionati con pesi sugli archi non negativi, e può essere usato su mappe geografiche ma anche come ausilio o base per algoritmi più complessi.
Ecco una spiegazione passo passo di uno dei più noti e celebri algoritmi di informatica.
Premesse:
- Grafo: Si parte da un grafo con nodi e archi.
- Nodo di partenza: Indica il nodo da cui inizia la ricerca del percorso più breve.
- Pesi sugli archi: Ogni arco ha un peso che indica la distanza o il costo tra due nodi collegati.
Passo 1: Inizializzazione
- Insieme dei nodi visitati: Inizialmente vuoto.
- Distanza dal nodo di partenza: Inizialmente, per tutti i nodi, eccetto il nodo di partenza, la distanza viene impostata a infinito.
- Distanza dal nodo di partenza a se stesso: È 0.
Passo 2: Scelta del nodo con la distanza minima
- Scegli il nodo con la distanza minima non ancora visitato: Inizia con il nodo di partenza.
- Calcola le distanze minime: Aggiorna la distanza minima da questo nodo ai suoi vicini considerando il peso degli archi e il percorso più breve attuale.
Passo 3: Aggiornamento delle distanze
- Per ogni nodo adiacente non ancora visitato: Calcola la distanza minima rispetto al nodo di partenza passando attraverso il nodo attuale.
- Aggiorna la distanza se la nuova distanza è minore di quella attuale: Se la nuova distanza è più breve, aggiorna il valore della distanza e l’informazione sul nodo precedente che ha portato a questa distanza più breve.
Passo 4: Marcatura del nodo visitato
- Marca il nodo attuale come visitato: Una volta terminato il calcolo delle distanze minime per tutti i nodi adiacenti, marca il nodo attuale come visitato e continua il processo scegliendo il prossimo nodo con la distanza minima non ancora visitato.
Passo 5: Ripeti finché tutti i nodi non sono visitati
- Continua il processo: Continua a scegliere il nodo con la distanza minima non visitato e aggiornare le distanze fino a quando tutti i nodi non sono stati visitati.
Passo 6: Ottieni il percorso più breve
- Recupera il percorso più breve per ogni nodo: Una volta che tutti i nodi sono stati visitati e le distanze minime sono state calcolate, è possibile recuperare il percorso più breve dal nodo di partenza a ogni altro nodo utilizzando le informazioni sui nodi precedenti.
E per finire…
- Alla fine dell’algoritmo, si otterranno le distanze minime da un nodo di partenza a tutti gli altri nodi nel grafo e i percorsi più brevi associati a ciascun nodo.
Implementazione in Python dell’algoritmo di Dijkstra
In questo esempio, graph è un dizionario che rappresenta il grafo con i nodi come chiavi e un altro dizionario interno che rappresenta i nodi collegati e i relativi pesi sugli archi.
L’algoritmo di Dijkstra utilizza una coda di priorità implementata con heapq per estrarre efficientemente il nodo con la distanza minima non visitato ad ogni iterazione. Il risultato restituito è un dizionario delle distanze minime dal nodo di partenza a tutti gli altri nodi nel grafo.
import heapq
def dijkstra(graph, start):
# Inizializzazione delle distanze, impostate tutte a infinito tranne il nodo di partenza
distances = {node: float('inf') for node in graph}
distances[start] = 0
# Coda di priorità per mantenere traccia dei nodi non visitati e delle loro distanze
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# Se abbiamo già trovato un percorso più breve per questo nodo, passiamo avanti
if current_distance > distances[current_node]:
continue
# Esplora i vicini del nodo corrente
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# Se la nuova distanza è più breve di quella attualmente nota
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# Esempio di utilizzo dell'algoritmo con un grafo di esempio
graph_example = {
'A': {'B': 5, 'C': 3},
'B': {'A': 5, 'C': 2, 'D': 1},
'C': {'A': 3, 'B': 2, 'D': 4},
'D': {'B': 1, 'C': 4}
}
start_node = 'A'
result = dijkstra(graph_example, start_node)
print("Distanze minime dal nodo di partenza '" + start_node + "':")
print(result)
Ecco un’implementazione di base dell’algoritmo di Dijkstra in Python utilizzando un dizionario per rappresentare il grafo e una coda di priorità per tenere traccia dei nodi non visitati con le relative distanze.
Foto: <a href=”https://commons.wikimedia.org/wiki/File:Edsger_Dijkstra_1994.jpg”>Andreas F. Borchert</a>, <a href=”https://creativecommons.org/licenses/by-sa/3.0/de/deed.en”>CC BY-SA 3.0 DE</a>, via Wikimedia Commons
