Algoritmo di Dijkstra — Cammino minimo passo dopo passo

L'algoritmo di Dijkstra trova i cammini minimi a partire da un nodo iniziale in un grafo pesato, purché ogni peso degli archi sia non negativo. Se ti interessa solo una destinazione, puoi fermarti non appena quella destinazione diventa definitiva.

L'idea centrale è greedy: si continua sempre dal nodo non ancora definitivo con la distanza nota più piccola. Questo funziona solo con la condizione dei pesi non negativi.

Cosa risolve l'algoritmo di Dijkstra

Usa l'algoritmo di Dijkstra quando hai un grafo con costi sugli archi e vuoi trovare il percorso meno costoso. Il costo può rappresentare distanza, tempo di viaggio, energia o un'altra quantità che vuoi minimizzare.

Funziona su grafi orientati o non orientati. La condizione chiave è esplicita: ogni peso degli archi deve essere almeno $0$.

Come funziona l'algoritmo

Ogni nodo mantiene una distanza provvisoria dal nodo iniziale. All'inizio, il nodo di partenza ha distanza $0$ e ogni altro nodo ha distanza $\infty$.

Poi si ripete questo ciclo:

1. Scegli il nodo non definitivo con la distanza provvisoria più piccola.
2. Controlla ogni vicino passando per quel nodo.
3. Se il nuovo percorso è meno costoso, aggiorna la distanza del vicino.
4. Segna il nodo corrente come definitivo.

Il passo 3 si chiama rilassamento. Un nodo definitivo è concluso: la sua distanza minima è finale, a condizione che il grafo non abbia archi con peso negativo.

Algoritmo di Dijkstra passo dopo passo

Ecco la procedura completa in forma compatta:

1. Scegli un nodo iniziale.
2. Imposta la sua distanza a $0$ e ogni altra distanza a $\infty$.
3. Seleziona il nodo non definitivo con la distanza provvisoria più piccola.
4. Rilassa i suoi archi uscenti.
5. Segna quel nodo come definitivo.
6. Ripeti finché tutti i nodi raggiungibili sono definitivi, oppure fermati quando il nodo obiettivo diventa definitivo.

Se memorizzi anche quale nodo precedente ha causato ogni aggiornamento, puoi ricostruire il percorso effettivo, non solo la distanza finale.

Esempio svolto di cammino minimo

Supponiamo che il grafo abbia questi pesi sugli archi:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Vogliamo il cammino minimo da $A$ a $D$.

Partiamo con:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Rendiamo definitivo $A$ per primo e rilassiamo i suoi archi:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

La distanza non definitiva più piccola è ora in $C$, quindi rendiamo definitivo $C$.

Passando per $C$:

• Passando per $C$, il cammino verso $B$ costa $1+2=3$, che migliora $4$, quindi aggiorniamo $\text{dist}(B)=3$.
• Passando per $C$, il cammino verso $D$ costa $1+5=6$, quindi impostiamo $\text{dist}(D)=6$.

Ora $B$ ha la distanza non definitiva più piccola, quindi rendiamo definitivo $B$.

Passando per $B$, il cammino verso $D$ costa:

$$3+1=4$$

Questo migliora $6$, quindi aggiorniamo $\text{dist}(D)$ da $6$ a $4$.

Ora $D$ è il nodo non definitivo più piccolo. Rendiamolo definitivo e fermiamoci.

Il cammino minimo è:

$$A \to C \to B \to D$$

con costo totale:

$$1+2+1=4$$

Questo esempio mostra il modello chiave: un percorso che all'inizio sembrava peggiore, $A \to B$, è diventato migliore più tardi passando per $C$. L'algoritmo di Dijkstra lo permette finché $B$ non è ancora definitivo. Una volta che un nodo è definitivo, la sua distanza non cambierà più.

Perché i pesi non negativi sono importanti

Supponiamo che il nodo non definitivo attualmente più economico abbia distanza $d$. Qualsiasi nuovo cammino verso quel nodo trovato più tardi dovrebbe provenire da un altro nodo non definitivo con distanza provvisoria almeno pari a $d$, e poi aggiungere un arco di peso almeno $0$.

Quindi quel percorso successivo non può battere $d$. Ecco perché rendere definitiva la distanza provvisoria più piccola è sicuro quando tutti i pesi sono non negativi.

Se esiste un arco negativo, questo ragionamento non vale più. Un cammino che ora sembra costoso potrebbe diventare più economico in seguito, quindi rendere definitivo un nodo troppo presto può dare una risposta sbagliata.

Errori comuni con l'algoritmo di Dijkstra

Usarlo con un arco negativo

Anche un solo arco negativo può rompere la logica greedy. Se sono possibili pesi negativi, usa un altro metodo per il cammino minimo.

Trattare "visto" come "finito"

Un nodo può avere già una distanza provvisoria ed essere comunque non ancora concluso. Solo un nodo definitivo ha una distanza minima finale.

Dimenticare la tabella dei nodi precedenti

Le distanze ti dicono il costo. Se vuoi anche il percorso vero e proprio, memorizza quale nodo ha migliorato per ultimo ogni distanza.

Dove si usa l'algoritmo di Dijkstra

L'algoritmo di Dijkstra si usa quando un problema può essere modellato come un movimento in un grafo con costi non negativi:

• Pianificazione dei percorsi sulle mappe
• Instradamento di rete
• Movimento di robot su griglie pesate
• Pathfinding nei giochi quando i costi di movimento variano

È anche un esempio classico di algoritmo greedy la cui correttezza dipende da una condizione precisa.

Prova un problema simile

Disegna un grafo con cinque nodi e pesi positivi sugli archi, poi esegui a mano l'algoritmo di Dijkstra con una tabella delle distanze. Se vuoi un buon passo successivo, prova una tua versione su un nuovo grafo e controlla esattamente quando ogni nodo diventa sicuro da rendere definitivo.