Implementare l'algoritmo di Dijkstra in Python: tutorial passo passo

Perché imparare l’algoritmo di Dijkstra?

Dijkstra è l’algoritmo di riferimento per trovare il percorso più breve tra due punti in una rete, con moltissime applicazioni. È fondamentale in informatica e nella teoria dei grafi. Capirlo e imparare a implementarlo apre la strada ad algoritmi e applicazioni su grafi più avanzati.

Insegna anche un prezioso approccio alla risoluzione dei problemi grazie alla sua natura greedy: a ogni passo si compie la scelta ottimale basandosi sulle informazioni correnti.

Questa abilità è trasferibile ad altri algoritmi di ottimizzazione. L’algoritmo di Dijkstra non è il più efficiente in tutti gli scenari, ma può essere un buon punto di partenza quando si affrontano problemi di “distanza minima”.

Esempi includono:

• Sistemi di navigazione GPS che trovano il percorso più veloce
• Instradamento dei pacchetti dati nelle reti informatiche
• Servizi di consegna che ottimizzano i percorsi per l’efficienza
• Social network (suggerimento di connessioni)
• Finanza (ricerca di percorsi di investimento ottimali)
• Project management (individuazione del flusso di lavoro più efficiente)

Anche se non ti interessano direttamente questi ambiti, implementare l’algoritmo di Dijkstra in Python ti permette di esercitarti con concetti importanti come:

• Classi in Python
• Dictionary comprehension
• List comprehension
• Code con priorità

Concetti chiave relativi ai grafi

Per implementare l’algoritmo di Dijkstra in Python, ripassiamo alcuni concetti essenziali di teoria dei grafi. Prima di tutto, i grafi stessi:

I grafi sono collezioni di nodi (vertici) collegati da archi. I nodi rappresentano entità o punti in una rete, mentre gli archi rappresentano le connessioni o le relazioni tra di essi.

I grafi possono essere pesati o non pesati. Nei grafi non pesati, tutti gli archi hanno lo stesso peso (spesso impostato a 1). Nei grafi pesati, ogni arco ha un peso associato, spesso rappresentando costo, distanza o tempo.

In questo tutorial useremo grafi pesati, perché sono necessari per l’algoritmo di Dijkstra.

Un percorso in un grafo è una sequenza di nodi collegati da archi, che inizia e finisce in nodi specifici. Il percorso più breve, che è ciò che ci interessa in questo tutorial, è quello con il peso totale minimo (distanza, costo, ecc.).

L’algoritmo di Dijkstra spiegato visivamente

Per il resto del tutorial useremo l’ultimo grafo visto:

Proviamo a trovare il percorso più breve tra i punti B e F usando l’algoritmo di Dijkstra, tra almeno sette percorsi possibili. All’inizio svolgeremo il compito visivamente, per poi implementarlo in codice.

Per prima cosa, inizializziamo l’algoritmo così:

1. Impostiamo B come nodo radice (sorgente).
2. Impostiamo le distanze tra B e tutti gli altri nodi a infinito come valori iniziali, provvisori. Impostiamo il valore di B a 0, perché è la distanza da sé stesso:

Poi, eseguiamo iterativamente i seguenti passi:

1. Scegli il nodo con il valore più piccolo come “nodo corrente” e visita tutti i suoi nodi vicini. Mentre visiti ciascun vicino, aggiorna i loro valori provvisori da infinito ai pesi degli archi a partire dalla sorgente.
2. Dopo aver visitato tutti i vicini del nodo corrente, marca il nodo corrente come “visitato”. Una volta che un nodo è marcato “visitato”, il suo valore è già il percorso più breve dalla sorgente.
3. L’algoritmo torna al passo 1 e sceglie il nodo con il valore più piccolo.

Nel nostro grafo, B ha tre vicini — A, D ed E. Visitiamoli a partire dal nodo radice e aggiorniamo i loro valori (iterazione 1) in base ai pesi degli archi:

Nell’iterazione 2 scegliamo di nuovo il nodo con il valore più piccolo, questa volta — E. I suoi vicini sono C, D e G. B è escluso perché lo abbiamo già visitato. Aggiorniamo i valori dei vicini di E:

Impostiamo il valore di C a 5.6 perché il suo valore è la somma cumulativa dei pesi da B a C. Lo stesso vale per G. Tuttavia, se ci fai caso, il valore di D rimane 3.5 quando avrebbe dovuto essere 3.5 + 2.8 = 6.3, come per gli altri nodi.

La regola è che, se la nuova somma cumulativa è maggiore del valore corrente del nodo, non lo aggiorniamo perché il nodo indica già la distanza minima dalla sorgente. In questo caso, il valore corrente di D pari a 3.5 indica già la distanza minima da B perché sono vicini.

Continuiamo in questo modo finché tutti i nodi sono visitati. Quando ciò avviene, avremo la distanza minima a ciascun nodo a partire da B e potremo semplicemente leggere il valore da B a F.

In sintesi, i passi sono:

1. Inizializza il grafo con il nodo sorgente a 0 e tutti gli altri a infinito. Parti dalla sorgente come “nodo corrente”.
2. Visita tutti i vicini del nodo corrente e aggiorna i loro valori alla somma cumulativa dei pesi (distanze) dalla sorgente. Se il valore corrente di un vicino è minore della somma cumulativa, rimane invariato. Marca il “nodo corrente” come completato.
3. Marca il nodo non completato con valore minimo come “nodo corrente”.
4. Ripeti i passi 2 e 3 finché tutti i nodi sono completati.

Implementazione passo passo dell’algoritmo di Dijkstra in Python

Ora, per consolidare la comprensione dell’algoritmo di Dijkstra, impariamo a implementarlo in Python passo dopo passo.

Capire i grafi come dizionari

Per prima cosa, ci serve un modo per rappresentare i grafi in Python — l’opzione più diffusa è usare un dizionario. Se questo è il nostro grafo:

Possiamo rappresentarlo con il seguente dizionario:

graph = {
   "A": {"B": 3, "C": 3},
   "B": {"A": 3, "D": 3.5, "E": 2.8},
   "C": {"A": 3, "E": 2.8, "F": 3.5},
   "D": {"B": 3.5, "E": 3.1, "G": 10},
   "E": {"B": 2.8, "C": 2.8, "D": 3.1, "G": 7},
   "F": {"G": 2.5, "C": 3.5},
   "G": {"F": 2.5, "E": 7, "D": 10},
}
Offerto da

Ogni chiave del dizionario è un nodo e ogni valore è un dizionario che contiene i vicini della chiave e le distanze verso di essi. Il nostro grafo ha sette nodi, quindi il dizionario deve avere sette chiavi.

Altre fonti spesso si riferiscono al dizionario sopra come a una lista di adiacenza in forma di dizionario. D’ora in poi useremo anche noi questo termine.

1. Creare una classe Graph

Per rendere il codice più modulare e facile da seguire, implementeremo una semplice classe Graph per rappresentare i grafi. Internamente userà una lista di adiacenza basata su dizionario. Avrà anche un metodo per aggiungere facilmente connessioni tra due nodi:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph  # A dictionary for the adjacency list

   def add_edge(self, node1, node2, weight):
       if node1 not in self.graph:  # Check if the node is already added
           self.graph[node1] = {}  # If not, create the node
       self.graph[node1][node2] = weight  # Else, add a connection to its neighbor
Offerto da

Usando questa classe, possiamo costruire il grafo iterativamente da zero così:

G = Graph()

# Add A and its neighbors
G.add_edge("A", "B", 3)
G.add_edge("A", "C", 3)

# Add B and its neighbors
G.add_edge("B", "A", 3)
G.add_edge("B", "D", 3.5)
G.add_edge("B", "E", 2.8)

...
Offerto da

Oppure possiamo passare direttamente una lista di adiacenza come dizionario, metodo più veloce:

# Use the dictionary we defined earlier
G = Graph(graph=graph)

G.graph
Offerto da

{'A': {'B': 3, 'C': 3},
'B': {'A': 3, 'D': 3.5, 'E': 2.8},
'C': {'A': 3, 'E': 2.8, 'F': 3.5},
'D': {'B': 3.5, 'E': 3.1, 'G': 10},
'E': {'B': 2.8, 'C': 2.8, 'D': 3.1, 'G': 7},
'F': {'G': 2.5, 'C': 3.5},
'G': {'F': 2.5, 'E': 7, 'D': 10}}
Offerto da

2. Usare un dizionario per memorizzare le distanze dalla sorgente

Creiamo un altro metodo della classe — questa volta per l’algoritmo stesso — shortest_distances:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   # The add_edge method omitted for space

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       ...
Offerto da

La prima cosa che facciamo all’interno del metodo è definire un dizionario che contiene coppie nodo-valore. Questo dizionario viene aggiornato ogni volta che visitiamo un nodo e i suoi vicini. Come menzionato nella spiegazione visiva dell’algoritmo, i valori iniziali di tutti i nodi sono impostati a infinito, mentre il valore della sorgente è 0.

Quando avremo finito di scrivere il metodo, questo dizionario verrà restituito e conterrà le distanze minime a tutti i nodi dalla sorgente. Potremo trovare la distanza da B a F così:

# Sneak-peek - find the shortest paths from B
distances = G.shortest_distances("B")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
Offerto da

3. Usare una coda con priorità per iterare sui nodi

Ora ci serve un modo per scorrere i nodi del grafo seguendo le regole dell’algoritmo di Dijkstra. Ricorda: a ogni iterazione dobbiamo scegliere il nodo con il valore più piccolo e visitare i suoi vicini.

Potresti dire che possiamo semplicemente scorrere le chiavi del dizionario:

for node in graph.keys():
   ...
Offerto da

Questo metodo non funziona perché non ci permette di ordinare i nodi in base al loro valore. Quindi, semplici array non bastano. Per risolvere questa parte del problema, useremo una coda con priorità.

Una coda con priorità è come una lista (array), ma ogni elemento ha un valore extra che rappresenta la sua priorità. Ecco un esempio di coda con priorità:

pq = [(3, "A"), (1, "C"), (7, "D")]Offerto da

Questa coda contiene tre elementi — A, C e D — e ciascuno ha un valore di priorità che determina il comportamento delle operazioni sulla coda. Python fornisce la libreria integrata heapq per lavorare con le code con priorità:

from heapq import heapify, heappop, heappushOfferto da

La libreria offre tre funzioni che ci interessano:

• heapify: trasforma una lista di tuple con coppie priorità-valore in una coda con priorità.
• heappush: aggiunge un elemento alla coda con la sua priorità associata.
• heappop: rimuove e restituisce l’elemento con priorità più alta (cioè l’elemento con il valore più piccolo).

pq = [(3, "A"), (1, "C"), (7, "D")]

# Convert into a queue object
heapify(pq)

# Return the highest priority value
heappop(pq)
Offerto da

(1, 'C')Offerto da

Come vedi, dopo aver convertito pq in una coda usando heapify, siamo riusciti a estrarre C in base alla sua priorità. Proviamo ad aggiungere un valore:

heappush(pq, (0, "B"))

heappop(pq)
Offerto da

(0, 'B')Offerto da

La coda è stata aggiornata correttamente in base alla priorità del nuovo elemento, perché heappop ha restituito il nuovo elemento con priorità 0.

Nota che, dopo aver estratto un elemento, non farà più parte della coda.

Ora, tornando al nostro algoritmo, dopo aver inizializzato distances, creiamo una nuova coda con priorità che contiene inizialmente solo il nodo sorgente:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()
Offerto da

La priorità di ciascun elemento in pq sarà il suo valore corrente. Inizializziamo anche un set vuoto per registrare i nodi visitati.

4. L’algoritmo di Dijkstra come ciclo while

Ora iniziamo a iterare su tutti i nodi non visitati usando un ciclo while:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()

       while pq:  # While the priority queue isn't empty
           current_distance, current_node = heappop(
               pq
           )  # Get the node with the min distance

           if current_node in visited:
               continue  # Skip already visited nodes
           visited.add(current_node)  # Else, add the node to visited set
Offerto da

Finché la coda con priorità non è vuota, estraiamo il nodo con priorità più alta (cioè con valore minimo) e otteniamo il suo valore e il suo nome in current_distance e current_node. Se current_node è già in visited, lo saltiamo. Altrimenti, lo marchiamo come visitato e passiamo a visitare i suoi vicini:

while pq:  # While the priority queue isn't empty
   current_distance, current_node = heappop(pq)

   if current_node in visited:
       continue 
   visited.add(current_node)

   for neighbor, weight in self.graph[current_node].items():
       # Calculate the distance from current_node to the neighbor
       tentative_distance = current_distance + weight
       if tentative_distance < distances[neighbor]:
           distances[neighbor] = tentative_distance
           heappush(pq, (tentative_distance, neighbor))

return distances
Offerto da

Per ciascun vicino calcoliamo la distanza provvisoria dal nodo corrente sommando il valore corrente al peso dell’arco. Poi verifichiamo se questa distanza è minore della distanza del vicino in distances. Se sì, aggiorniamo il dizionario distances e aggiungiamo il vicino con la sua distanza provvisoria alla coda con priorità.

Ecco fatto! Abbiamo implementato l’algoritmo di Dijkstra. Testiamolo:

G = Graph(graph)

distances = G.shortest_distances("B")
print(distances, "\n")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
Offerto da

{'A': 3, 'B': 0, 'C': 5.6, 'D': 3.5, 'E': 2.8, 'F': 9.1, 'G': 9.8}

The shortest distance from B to F is 9.1
Offerto da

Quindi, la distanza da B a F è 9.1. Ma aspetta: qual è il percorso?

5. Costruire il percorso più breve

Al momento abbiamo solo le distanze minime, non i percorsi, per cui il nostro grafo appare così:

Per costruire il percorso più breve a partire dalla distanza minima calcolata, possiamo effettuare il backtracking dal nodo di arrivo. Per ciascun arco collegato a F, sottraiamo il suo peso:

1. 9.1–3.5 = 5.6
2. 9.1–2.5 = 6.5

Poi verifichiamo se uno dei risultati corrisponde al valore dei vicini di F. Solo 5.6 corrisponde al valore di C, il che significa che C fa parte del percorso più breve.

Ripetiamo il processo per i vicini di C, A ed E:

1. 5.6–3 = 2.6
2. 5.6–2.8 = 2.8

Poiché 2.8 corrisponde al valore di E, anche E fa parte del percorso più breve. E inoltre E è vicino di B, il che rende il percorso più breve tra B e F — BECF.

Aggiungiamo l’implementazione di questo processo alla nostra classe. Il codice è leggermente diverso da quanto spiegato sopra perché trova i percorsi più brevi tra B e tutti gli altri nodi, non solo F.

Lo fa anche al contrario, ma l’idea è la stessa.

Aggiungi le seguenti righe di codice alla fine del metodo shortest_distances eliminando il vecchio return:

predecessors = {node: None for node in self.graph}

for node, distance in distances.items():
   for neighbor, weight in self.graph[node].items():
       if distances[neighbor] == distance + weight:
           predecessors[neighbor] = node

return distances, predecessors
Offerto da

Quando il codice viene eseguito, il dizionario predecessors contiene il genitore immediato di ciascun nodo coinvolto nel percorso più breve verso la sorgente. Proviamolo:

G = Graph(graph)

distances, predecessors = G.shortest_distances("B")

print(predecessors)
Offerto da

{'A': 'B', 'B': None, 'C': 'E', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'E'}Offerto da

Per prima cosa, troviamo manualmente il percorso più breve usando il dizionario predecessors facendo backtracking da F:

# Check the predecessor of F
predecessors["F"]
Offerto da

'C'  # It is COfferto da

# Check the predecessor of C
predecessors["C"]
Offerto da

'E'  # It is EOfferto da

# Check the predecessor of E
predecessors["E"]
Offerto da

'B'  # It is BOfferto da

Ecco! Il dizionario ci indica correttamente che il percorso più breve tra B e F è BECF.

Ma lo abbiamo trovato in modo semi-manuale. Vogliamo un metodo che restituisca automaticamente il percorso più breve costruito dal dizionario predecessors da qualsiasi sorgente a qualsiasi destinazione. Definiamo questo metodo come shortest_path (aggiungilo alla fine della classe):

def shortest_path(self, source: str, target: str):
   # Generate the predecessors dict
   _, predecessors = self.shortest_distances(source)

   path = []
   current_node = target

   # Backtrack from the target node using predecessors
   while current_node:
       path.append(current_node)
       current_node = predecessors[current_node]

   # Reverse the path and return it
   path.reverse()

   return path
Offerto da

Usando la funzione shortest_distances generiamo il dizionario predecessors. Poi avviamo un ciclo while che risale di un nodo alla volta a partire dalla destinazione finché non raggiunge la sorgente. Quindi restituiamo la lista invertita, che contiene il percorso dalla sorgente alla destinazione.

Testiamolo:

G = Graph(graph)

G.shortest_path("B", "F")
Offerto da

['B', 'E', 'C', 'F']Offerto da

Funziona! Proviamone un altro:

G.shortest_path("A", "G")Offerto da

['A', 'C', 'F', 'G']Offerto da

Perfetto.

Conclusione

In questo tutorial abbiamo imparato uno degli algoritmi più fondamentali della teoria dei grafi — quello di Dijkstra. È spesso l’algoritmo di riferimento per trovare il percorso più breve tra due punti in strutture simili a grafi. Grazie alla sua semplicità, trova applicazione in molte industrie, tra cui:

• Logistica e trasporti
• Networking e telecomunicazioni
• Manifattura e robotica
• Finanza e investimenti
• Pianificazione urbana

Spero che implementare l’algoritmo di Dijkstra in Python abbia acceso il tuo interesse per il meraviglioso mondo degli algoritmi su grafi. Se vuoi approfondire, ti consiglio vivamente le seguenti risorse:

• Corso Introduction to Network Analysis in Python
• Corso Data Structures And Algorithms in Python