9.1 Principi di funzionamento dell'algoritmo di Dijkstra
L'algoritmo di Dijkstra è un algoritmo per trovare i percorsi più brevi dal nodo iniziale a tutti gli altri nodi in un grafo con pesi non negativi sugli archi. L'algoritmo utilizza un approccio greedy, scegliendo a ogni passo il nodo con la distanza più piccola nota dal nodo iniziale e aggiornando le distanze ai nodi adiacenti.
Fasi dell'algoritmo:
1. Inizializzazione:
- Impostiamo la distanza al nodo iniziale pari a 0.
- Impostiamo la distanza a tutti gli altri nodi pari all'infinito.
- Creiamo un insieme di nodi non visitati.
2. Scelta del nodo corrente:
- Scegliamo un nodo non visitato con la distanza più piccola (il nodo iniziale al primo passo).
3. Aggiornamento delle distanze:
- Per ogni nodo adiacente a quello corrente, se il nuovo percorso attraverso il nodo corrente è più corto del percorso noto, aggiorniamo la distanza a quel nodo.
4. Segniamo il nodo corrente come visitato:
- Rimuoviamo il nodo corrente dall'insieme dei nodi non visitati.
5. Ripetiamo i passi 2-4, fino a quando non vengono visitati tutti i nodi o non raggiungiamo il nodo di destinazione.
Complessità temporale e spaziale dell'algoritmo di Dijkstra:
Complessità temporale:
O((V + E) log V) quando si utilizza una coda con priorità (per esempio, un heap di Fibonacci), dove V è il numero di nodi, E è il numero di archi.
O(V^2) quando si utilizza una lista semplice per memorizzare le distanze.
Complessità spaziale:
O(V) per memorizzare le distanze e i predecessori (per ricostruire il percorso).
9.2 Implementazione dell'algoritmo di Dijkstra
L'implementazione dell'algoritmo di Dijkstra è lunga, ma molto semplice. Ti consiglio di provare a capirla. Se non è chiaro, torna indietro e rileggi i passaggi principali dell'algoritmo.
Ecco un esempio di implementazione dell'algoritmo di Dijkstra utilizzando una coda di priorità (heap):
import heapq
def dijkstra(graph, start):
# Inizializzazione
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
parents = {vertex: None for vertex in graph}
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
# Se la distanza attuale è maggiore di quella registrata, saltiamo il nodo
if current_distance > distances[current_vertex]:
continue
# Aggiornamento delle distanze ai nodi adiacenti
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# Se viene trovato un percorso più breve al nodo adiacente
if distance < distances[neighbor]:
distances[neighbor] = distance
parents[neighbor] = current_vertex
heapq.heappush(priority_queue, (distance, neighbor))
return distances, parents
# Esempio di utilizzo:
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
start_vertex = 'A'
distances, parents = dijkstra(graph, start_vertex)
print("Distanze più brevi dal nodo iniziale:", distances)
print("Predecessori per il recupero del percorso:", parents)
Output:
Distanze più brevi dal nodo iniziale: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Predecessori per il recupero del percorso: {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}
9.3 Esempi di problemi risolti con l'algoritmo di Dijkstra
Esempi classici di problemi risolti con l'algoritmo di Dijkstra:
1. Ottimizzazione dei percorsi nelle reti di trasporto
Trovare il percorso più breve tra punti in una rete di trasporto (ad esempio, tra città).
Applicazione:
Sistemi di navigazione, come Google Maps, utilizzano l'algoritmo di Dijkstra per calcolare i percorsi ottimali.
2. Pianificazione dei percorsi di consegna
Ottimizzazione dei percorsi per i servizi di consegna di merci, al fine di ridurre i costi e il tempo di consegna.
Applicazione:
Le aziende di logistica utilizzano l'algoritmo di Dijkstra per la pianificazione dei percorsi di consegna e la riduzione dei costi operativi.
3. Gestione delle reti
Ottimizzazione dell'instradamento dei pacchetti di dati nelle reti informatiche per minimizzare i ritardi e aumentare la capacità.
Applicazione:
I protocolli di routing, come OSPF (Open Shortest Path First), utilizzano l'algoritmo di Dijkstra per trovare i percorsi più brevi nelle reti.
4. Analisi delle reti sociali
Trovare percorsi più brevi e misurare la centralità nei grafi sociali (ad esempio, per trovare gli utenti più influenti).
Applicazione:
Le piattaforme social analizzano le connessioni tra gli utenti per fornire raccomandazioni e analizzare l'attività di rete.
5. Giochi e mondi virtuali
Trovare il percorso per i personaggi nei mondi di gioco con ostacoli e diversi livelli di difficoltà.
Applicazione:
I motori di gioco utilizzano l'algoritmo di Dijkstra per calcolare i movimenti di personaggi e oggetti nei mondi virtuali.
6. Sistemi di gestione dell'energia
Ottimizzazione della distribuzione dell'energia nelle reti elettriche per minimizzare le perdite e garantire l'affidabilità delle forniture.
Applicazione:
Le aziende elettriche utilizzano l'algoritmo di Dijkstra per ottimizzare i percorsi di trasmissione dell'energia nelle reti, al fine di minimizzare le perdite di energia ed evitare sovraccarichi.
Esempio:
Nelle reti elettriche, ogni nodo rappresenta una sottostazione e gli archi sono linee elettriche con diversi livelli di resistenza. L'algoritmo di Dijkstra aiuta a trovare il percorso con la minore resistenza dalla fonte di energia al consumatore.
7. Sistemi di evacuazione e pianificazione del percorso
Ottimizzazione dei percorsi di evacuazione negli edifici o nelle città per un'uscita rapida e sicura in caso di emergenze.
Applicazione:
Architetti e ingegneri utilizzano l'algoritmo di Dijkstra per pianificare i percorsi di evacuazione, per garantire la rimozione sicura e veloce delle persone dalle aree pericolose.
Esempio:
In un condominio o in un edificio per uffici, i nodi del grafo rappresentano le stanze e i corridoi, e gli archi sono i percorsi tra di essi. L'algoritmo di Dijkstra può essere utilizzato per trovare il percorso più breve da qualsiasi punto nell'edificio all'uscita più vicina.
GO TO FULL VERSION