Tre domande diverse, tre algoritmi: come arrivare con meno passaggi, come spendere meno lungo un percorso e come collegare tutti i punti con il costo totale minimo. Usiamo lo stesso grafo per distinguere con precisione questi obiettivi.
Un grafo è formato da vertici V e archi E. Il nostro è semplice, non orientato e connesso: un collegamento si percorre in entrambi i sensi. Ha 6 vertici e 9 archi. I numeri sugli archi sono costi, non lunghezze del disegno. Esaminiamo i vicini in ordine alfabetico; a parità di peso ordiniamo gli archi per nome. Un cammino collega due vertici; un ciclo torna al punto iniziale senza ripetere gli altri vertici. Un albero è connesso e privo di cicli.
A–B: 4 A–C: 2 B–C: 1 B–D: 5 C–D: 8 C–E: 10 D–E: 2 D–F: 6 E–F: 3
Linee verdi continue: archi scelti o predecessori correnti; linee grigie tratteggiate: altri archi. In BFS i pesi sono omessi. In Dijkstra i predecessori intermedi possono cambiare. ∞ indica una distanza non ancora trovata.
1. BFS: il minor numero di passaggi
La visita in ampiezza ignora i pesi. Tutti gli archi valgono un passaggio. Partiamo da A e cerchiamo la distanza, misurata in numero di archi, verso ogni vertice. La coda FIFO estrae per primo chi è entrato per primo.
Assegna d(A)=0 e inserisci A nella coda. Estrai il primo vertice u; per ogni vicino v non ancora scoperto, assegna d(v)=d(u)+1, registra u come predecessore e inserisci v in coda. Marca v già quando lo inserisci, non quando lo estrai, per evitare duplicati. Ripeti finché la coda è vuota.
| Passo | Vertice / arco | Coda / insieme definitivo / costo | Distanze in ordine A, B, C, D, E, F |
|---|---|---|---|
| 0 | — | [A] | 0, ∞, ∞, ∞, ∞, ∞ |
| 1 | A | [B, C] | 0, 1, 1, ∞, ∞, ∞ |
| 2 | B | [C, D] | 0, 1, 1, 2, ∞, ∞ |
| 3 | C | [D, E] | 0, 1, 1, 2, 2, ∞ |
| 4 | D | [E, F] | 0, 1, 1, 2, 2, 3 |
| 5 | E | [F] | 0, 1, 1, 2, 2, 3 |
| 6 | F | [] | 0, 1, 1, 2, 2, 3 |
Dopo A la coda è [B,C]. B scopre D; C scopre E, ma non riscrive D. D scopre F. Risultato: A–B–D–F ha 3 archi. Anche A–C–E–F ne ha 3: la soluzione può non essere unica. Il primo cammino costa 15, quindi meno passaggi non significa minor costo.
Perché funziona
- Invariante: la coda contiene vertici in ordine di distanza non decrescente; mentre si tratta il livello k, i nuovi vertici entrano in fondo al livello k+1.
- Base: A è al livello 0, corretto. Passo induttivo: se tutti i vertici fino al livello k hanno distanza corretta, ogni nuovo vicino di un vertice di livello k è raggiungibile in k+1 archi.
- Non può avere distanza minore: un suo predecessore su un cammino più corto sarebbe stato elaborato a un livello precedente e lo avrebbe già scoperto. Perciò la prima distanza assegnata è minima. I predecessori ricostruiscono un cammino minimo.
Con liste di adiacenza ogni vertice entra una volta e ogni arco viene esaminato due volte: tempo O(|V|+|E|), memoria ausiliaria O(|V|), oltre al grafo. In un grafo non connesso, da A si visita solo la sua componente.
Princeton · Algorithms, 4th Edition — BFS
2. Dijkstra: il cammino di costo minimo
Ora i pesi contano. Sono tutti non negativi: è l’ipotesi decisiva. d(v) è il costo del miglior cammino finora trovato, inizialmente infinito tranne d(A)=0. L’insieme S raccoglie i vertici con distanza definitiva.
Scegli fuori da S il vertice u con d(u) minimo. Inseriscilo in S. Per ogni vicino v ancora fuori da S, prova il rilassamento: d(v) ← min(d(v), d(u)+w(u,v)). Se migliora, aggiorna il predecessore di v. Continua; se il minimo è infinito, i vertici restanti sono irraggiungibili.
| Passo | Vertice / arco | Coda / insieme definitivo / costo | Distanze in ordine A, B, C, D, E, F |
|---|---|---|---|
| 0 | — | {} | 0, ∞, ∞, ∞, ∞, ∞ |
| 1 | A | {A} | 0, 4, 2, ∞, ∞, ∞ |
| 2 | C | {A, C} | 0, 3, 2, 10, 12, ∞ |
| 3 | B | {A, C, B} | 0, 3, 2, 8, 12, ∞ |
| 4 | D | {A, C, B, D} | 0, 3, 2, 8, 10, 14 |
| 5 | E | {A, C, B, D, E} | 0, 3, 2, 8, 10, 13 |
| 6 | F | {A, C, B, D, E, F} | 0, 3, 2, 8, 10, 13 |
Dopo A: B=4 e C=2. C migliora B a 3, propone D=10 ed E=12. B migliora D a 8. D migliora E a 10 e propone F=14. E migliora F a 13. Il cammino ottimo A–C–B–D–E–F costa 2+1+5+2+3=13, ma usa 5 archi: più del cammino BFS.
Perché funziona
- Ogni distanza finita è il costo di un cammino realmente trovato: non sottostima quindi il costo ottimo. Supponiamo corrette le distanze già rese definitive in S.
- Se il vertice minimo u avesse un cammino più economico, prendiamo il primo vertice y di quel cammino fuori da S e il suo predecessore x in S. Quando x è stato elaborato, il rilassamento ha assegnato a y un costo non superiore a quello del prefisso del cammino.
- Poiché i pesi restanti sono non negativi, quel prefisso costa al massimo l’intero cammino verso u. Quindi d(y) sarebbe minore di d(u), contro la scelta del minimo. La distanza di u è definitiva; per induzione lo sono tutte quelle estratte.
Con liste di adiacenza e heap binario con decrease-key: O((|V|+|E|) log |V|), memoria ausiliaria O(|V|). Una versione che cerca il minimo scandendo i vertici costa O(|V|²+|E|). Con pesi negativi la dimostrazione non vale: nel grafo orientato A→B=2, A→C=5, C→B=−10, B verrebbe fissato a 2 ma il vero minimo è −5.
Princeton · Algorithms, 4th Edition — Dijkstra
3. Kruskal: collegare tutto al minor costo
Non cerchiamo un percorso da A a F: vogliamo una rete che colleghi tutti i vertici minimizzando la somma dei pesi degli archi scelti. È un albero ricoprente minimo (MST). Un albero su 6 vertici ha esattamente 5 archi.
Ordina gli archi per peso crescente. Parti con ogni vertice in una componente separata. Accetta un arco solo se unisce due componenti diverse; altrimenti formerebbe un ciclo. Una struttura Union-Find controlla e fonde le componenti. Fermati dopo |V|−1 archi accettati.
| Passo | Vertice / arco | Coda / insieme definitivo / costo | Kruskal |
|---|---|---|---|
| 0 | — | 0 | — |
| 1 | BC (1) | 1 | Scelto |
| 2 | AC (2) | 3 | Scelto |
| 3 | DE (2) | 5 | Scelto |
| 4 | EF (3) | 8 | Scelto |
| 5 | AB (4) | 8 | Scartato: ciclo |
| 6 | BD (5) | 13 | Scelto |
Ordine iniziale: BC(1), AC(2), DE(2), EF(3), AB(4), BD(5). AB viene scartato perché A e B sono già collegati attraverso C: chiuderebbe il triangolo A–C–B–A. BD collega infine {A,B,C} a {D,E,F}. Costo totale 1+2+2+3+5=13. Gli archi DF(6), CD(8), CE(10) non servono più.
Perché funziona: argomento di scambio
- Invariante: esiste un albero ricoprente minimo T che contiene tutti gli archi finora scelti F. All’inizio F è vuoto, quindi è vero. Sia e il prossimo arco accettato, tra due componenti diverse di F.
- Se e è già in T, non cambia nulla. Altrimenti aggiungendolo a T nasce un unico ciclo. Su quel ciclo c’è un arco f che esce dalla componente di uno degli estremi di e; f non appartiene a F. Inoltre w(f)≥w(e): un arco più leggero che attraversasse quella componente sarebbe stato considerato prima e avrebbe unito le componenti.
- Sostituiamo f con e: la rete resta un albero e il costo non aumenta. Per minimalità di T, anche il nuovo albero è minimo e contiene F insieme a e. L’invariante continua. Dopo |V|−1 scelte il nostro albero coincide con un MST.
Ordinamento O(|E| log |E|); Union-Find con compressione dei cammini e unione per rango richiede complessivamente O(|E| α(|V|)), quasi lineare. Memoria O(|V|+|E|) includendo gli archi ordinati. Kruskal ammette anche pesi negativi. Se il grafo è sconnesso produce una foresta ricoprente minima, non un unico albero.
Princeton · Algorithms, 4th Edition — Kruskal
Attenzione: in questo esempio Dijkstra e Kruskal danno entrambi 13 e lo stesso insieme di archi, ma è una coincidenza. Nel triangolo AB=2, AC=2, BC=1, l’albero dei cammini minimi da A usa AB e AC (totale 4); un MST usa BC e uno dei due archi di peso 2 (totale 3). Nel secondo, uno dei cammini da A costa 3 invece di 2. Obiettivo diverso, risposta diversa.