Qual è il percorso più breve per andare da Rotterdam a Groninga? È 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.
Conclusione
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
Trovalost esiste da 4692 giorni (13 anni), e contiene ad oggi 4356 articoli (circa 3.484.800 parole in tutto) e 23 servizi online gratuiti. – Leggi un altro articolo a caso
Ho creato Trovalost.it e ho scritto quasi tutti i suoi contenuti relativi all'informatica. Credits immagini: pexels.com, pixabay.com, wikipedia.org, Midjourney, StarryAI, se non diversamente specificato.
Utilizziamo tecnologie come i cookie per memorizzare e/o accedere alle informazioni del dispositivo. Lo facciamo per migliorare l'esperienza di navigazione e per mostrare annunci personalizzati. Il consenso a queste tecnologie ci consentirà di elaborare dati quali il comportamento di navigazione o gli ID univoci su questo sito. Il mancato consenso o la revoca del consenso possono influire negativamente su alcune caratteristiche e funzioni.
Funzionale
Sempre attivo
L'archiviazione tecnica o l'accesso sono strettamente necessari al fine legittimo di consentire l'uso di un servizio specifico esplicitamente richiesto dall'abbonato o dall'utente, o al solo scopo di effettuare la trasmissione di una comunicazione su una rete di comunicazione elettronica.
Preferenze
L'archiviazione tecnica o l'accesso sono necessari per lo scopo legittimo di memorizzare le preferenze che non sono richieste dall'abbonato o dall'utente.
Statistiche
L'archiviazione tecnica o l'accesso che viene utilizzato esclusivamente per scopi statistici.L'archiviazione tecnica o l'accesso che viene utilizzato esclusivamente per scopi statistici anonimi. Senza un mandato di comparizione, una conformità volontaria da parte del vostro Fornitore di Servizi Internet, o ulteriori registrazioni da parte di terzi, le informazioni memorizzate o recuperate per questo scopo da sole non possono di solito essere utilizzate per l'identificazione.
Marketing
L'archiviazione tecnica o l'accesso sono necessari per creare profili di utenti per inviare pubblicità, o per tracciare l'utente su un sito web o su diversi siti web per scopi di marketing simili.