1. Il problema

In un grafo orientato e pesato G = (V, E), il peso di un cammino è la somma dei pesi dei suoi archi. Fissata una sorgente s, vogliamo conoscere il peso migliore per ogni vertice raggiungibile v e, tramite i predecessori, ricostruire un cammino che lo realizza.

2. L’operazione comune: rilassare un arco

Manteniamo una stima d[v] del costo minimo da s a v: d[s] = 0 e d[v] = +∞ per gli altri vertici. Se un cammino già noto verso u seguito dall’arco u → v migliora la stima di v, aggiorniamo distanza e predecessore.

Aggiorniamo anche prev[v] = u. Per ricostruire il percorso verso t, risaliamo i predecessori da t fino a s e invertiamo la sequenza. Se d[t] = +∞, t non è raggiungibile.

3. Dijkstra: pesi non negativi

Dijkstra sceglie ogni volta il vertice non ancora definitivo con la stima minore, poi rilassa i suoi archi uscenti. Tutti gli archi raggiungibili devono avere peso ≥ 0: altrimenti un percorso scoperto più tardi potrebbe migliorare un vertice già estratto.

d[s] = 0; ogni altro d[v] = +∞; prev[v] = indefinito
inserisci (0, s) nella coda di priorità minima
finché la coda non è vuota:
    estrai (costo, u)
    se costo ≠ d[u]: continua  // voce superata
    per ogni arco u → v di peso w:
        se d[u] + w < d[v]:
            d[v] = d[u] + w; prev[v] = u
            inserisci (d[v], v)

Esempio: s → a (4), s → b (1), b → a (2), a → t (1), b → t (7). L’ordine delle estrazioni valide è s, b, a, t. Da s otteniamo a = 4 e b = 1; da b miglioriamo a a 3 e troviamo t = 8; da a miglioriamo t a 4.

Il cammino minimo verso t è s → b → a → t e pesa 1 + 2 + 1 = 4. La scelta greedy è sicura perché aggiungere archi non negativi non può creare un percorso futuro più economico verso un vertice già estratto.

4. Bellman–Ford: pesi negativi e cicli

Bellman–Ford rilassa tutti gli archi per |V| − 1 passate. Dopo la passata k, le stime sono ottime per i cammini che usano al massimo k archi. Un cammino semplice ha al massimo |V| − 1 archi; perciò queste passate bastano se non esistono cicli negativi raggiungibili.

d[s] = 0; ogni altro d[v] = +∞
ripeti |V| − 1 volte:
    per ogni arco u → v di peso w:
        se d[u] è finito e d[u] + w < d[v]:
            d[v] = d[u] + w; prev[v] = u
    se nessuna stima è cambiata: termina le passate
per ogni arco u → v di peso w:
    se d[u] è finito e d[u] + w < d[v]:
        segnala un ciclo negativo raggiungibile

Esempio con un arco negativo: s → a (4), s → b (5), a → t (2), b → t (6), b → a (−3). Scorrendo gli archi in quest’ordine, la prima passata dà a = 2 e t = 6; la seconda migliora t a 4. Il risultato è s → b → a → t, peso 5 − 3 + 2 = 4. La versione di Dijkstra che rende definitivi i vertici estratti fisserebbe a al costo 4 troppo presto.

Per esempio, s → a (1), a → b (−2), b → a (1), b → t (2): a → b → a pesa −1. Ripetendolo prima di arrivare a t, il costo verso a, b e t scende senza limite.

5. Cammini massimi: il caso risolvibile in modo lineare

In un DAG (grafo orientato aciclico) ogni cammino è semplice. Calcoliamo un ordinamento topologico, poniamo L[s] = 0 e L[v] = −∞ per gli altri vertici, poi percorriamo i vertici in tale ordine. Per ogni arco u → v aggiorniamo L[v] = max(L[v], L[u] + w(u,v)) se L[u] è finito. Salviamo il predecessore quando miglioriamo la stima.

Funziona anche con pesi negativi: l’assenza di cicli è la condizione essenziale. Nello stesso DAG, sostituire max con min e −∞ con +∞ calcola i cammini minimi in O(|V| + |E|).

Il cammino massimo è s → a → b → t, peso 3 + 4 + 5 = 12. Su grafi generali, cambiare segno ai pesi e applicare Bellman–Ford risolve la variante con passeggiate solo se non ci sono cicli positivi raggiungibili; non risolve il problema del cammino semplice massimo, che in generale è NP-difficile.

6. Quale algoritmo?

I limiti usano liste di adiacenza e grafi semplici; per Dijkstra assumono una coda di priorità binaria. I tempi includono i vertici anche se il grafo è disconnesso. Bellman–Ford può terminare prima quando una passata non cambia nulla, ma il caso peggiore resta O(|V| + |V|·|E|).

Un albero ricoprente minimo collega tutti i vertici spendendo il meno possibile sull’intera rete; non garantisce i cammini più brevi da s. Vedi minimum spanning tree.

7. Errori ed esercizi

• Usare Dijkstra con archi negativi: anche un solo arco può invalidare la scelta definitiva.
• Scambiare +∞ e −∞: il primo è il valore iniziale del minimo, il secondo quello del massimo nei DAG.
• Ignorare la raggiungibilità: un ciclo negativo in una componente irraggiungibile da s non altera le distanze da s.