Ogni volta che un navigatore calcola un percorso, che un protocollo di instradamento sceglie la strada di un pacchetto o che un videogioco muove un personaggio verso un obiettivo, dietro c'è quasi sempre una variante dello stesso problema: trovare il cammino di costo minimo in un grafo pesato. L'algoritmo più noto per risolverlo è quello pubblicato da Edsger Dijkstra nel 1959, ed è ancora oggi il punto di riferimento quando i pesi degli archi non sono negativi.
Il problema
Dato un grafo con archi pesati (distanze, tempi, costi) e un vertice di partenza s, si vuole conoscere la distanza minima da s a ogni altro vertice, insieme al cammino che la realizza. La visita in ampiezza risolve il caso in cui tutti gli archi pesano uguale; con pesi diversi serve qualcosa di più.
Il rilassamento
L'operazione elementare è il rilassamento di un arco (u, v) di peso w: se passare da u migliora la stima attuale di v, la si aggiorna.
se dist[u] + w < dist[v]:
dist[v] = dist[u] + w
padre[v] = u
All'inizio dist[s] = 0 e tutte le altre stime valgono infinito. Gli algoritmi di cammino minimo differiscono solo nell'ordine in cui rilassano gli archi.
La strategia di Dijkstra
Dijkstra sceglie un ordine molto preciso: a ogni passo prende il vertice non ancora definitivo con la stima più bassa, lo dichiara definitivo e rilassa i suoi archi uscenti. L'intuizione è la stessa delle onde nello stagno della BFS, ma l'onda avanza per distanza effettiva e non per numero di archi.
Per trovare velocemente il vertice con la stima minima si usa una coda di priorità, tipicamente un heap binario:
import heapq
def dijkstra(adj, s):
dist = {s: 0}
padre = {s: None}
heap = [(0, s)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # voce superata da una stima migliore
for v, w in adj[u]:
nd = d + w
if v not in dist or nd < dist[v]:
dist[v] = nd
padre[v] = u
heapq.heappush(heap, (nd, v))
return dist, padre
La riga con continue merita attenzione. Il modulo heapq di Python non permette di diminuire la priorità di un elemento già inserito; allora si inserisce una nuova voce e, quando la vecchia emerge, la si scarta. È la tecnica detta «lazy deletion», semplice e molto efficiente in pratica.
Un esempio a mano
Vertici A, B, C, D; archi A–B 4, A–C 1, C–B 2, B–D 1, C–D 5. Partenza da A.
| Passo | Vertice reso definitivo | Stime dopo il rilassamento |
|---|---|---|
| 1 | A (0) | B = 4, C = 1 |
| 2 | C (1) | B = 3 (via C), D = 6 |
| 3 | B (3) | D = 4 (via B) |
| 4 | D (4) | — |
Il cammino minimo verso D è A → C → B → D, lungo 4, anche se usa tre archi invece dei due di A → C → D.
Perché servono pesi non negativi
La correttezza poggia su un'affermazione: quando un vertice viene estratto con la stima più bassa, nessun percorso alternativo può fare meglio, perché qualunque altro percorso passa da vertici con stima almeno uguale e aggiunge archi di peso positivo o nullo.
Se esiste un arco negativo, questa garanzia salta: un percorso che sembrava più lungo potrebbe diventare più corto dopo un arco di peso −5. Dijkstra può quindi restituire risultati sbagliati senza alcun segnale d'allarme. Con pesi negativi si usa Bellman-Ford.
Costo
Con un heap binario ogni estrazione e ogni inserimento costano un tempo logaritmico. Il totale è dell'ordine di (n + m) log n, eccellente per grafi sparsi come le reti stradali. Per grafi densi una versione con un semplice array, che cerca il minimo scorrendo tutti i vertici, costa n² e può essere persino più rapida.
Consigli pratici
- Fermatevi presto: se interessa un solo obiettivo t, si può interrompere l'algoritmo appena t viene estratto dall'heap. La sua distanza è già definitiva.
- Scegliete il peso giusto: lo stesso grafo stradale dà percorsi diversi se il peso è la lunghezza, il tempo medio o il costo del pedaggio. Si possono anche combinare, per esempio tempo più una penalità per ogni svolta.
- Attenzione ai valori in virgola mobile: confrontare somme di numeri decimali può creare differenze minime che cambiano il percorso scelto; se possibile si usano interi (metri, secondi).
- Grafi enormi: per reti continentali si aggiungono tecniche di preelaborazione, come la ricerca bidirezionale o l'uso di euristiche, di cui A* è l'esempio più noto.
In sintesi
- Dijkstra calcola i cammini minimi da una sorgente in grafi con pesi non negativi.
- A ogni passo rende definitivo il vertice con la stima più bassa e rilassa i suoi archi.
- Con un heap binario costa circa (n + m) log n.
- Con archi negativi può sbagliare senza accorgersene: in quel caso serve Bellman-Ford.
- Interrompere la ricerca all'arrivo e scegliere bene i pesi sono le ottimizzazioni più semplici.
