Un grafo è formato da nodi e archi. Ogni arco del nostro esempio ha un peso positivo, cioè un costo: può rappresentare chilometri, tempo o energia. Consideriamo grafi non orientati e connessi: da ogni nodo si può raggiungere ogni altro nodo.
La stessa rete pone domande differenti. Dijkstra cerca il percorso meno costoso da una partenza agli altri nodi. Prim e Kruskal cercano invece un albero che collega tutti i nodi senza cicli e con la minore somma dei pesi. Un percorso minimo e un albero minimo non sono lo stesso oggetto.
Un piccolo esempio comune
Immagina quattro nodi A, B, C, D e gli archi A–B di peso 4, A–C di peso 2, B–C di peso 1, B–D di peso 5 e C–D di peso 8. Da A a D, il percorso A–C–B–D costa 2+1+5=8; A–B–D costa 9 e A–C–D costa 10. Un albero minimo sceglie B–C, A–C e B–D, con peso totale 1+2+5=8. Il valore 8 coincide qui per caso: nel primo problema misura un solo percorso; nel secondo la rete che collega tutti.
1. Dijkstra: fissare distanze sempre più certe
Si parte con distanza 0 per il nodo iniziale e distanza provvisoria infinita per gli altri. A ogni passo si sceglie il nodo non ancora fissato con la distanza provvisoria più piccola. Poi si prova a migliorare le distanze dei vicini sommando il peso dei relativi archi. Con pesi non negativi, la distanza del nodo scelto è definitiva. Nel piccolo esempio, da A scopriamo C a costo 2 e B a costo 4; passando per C miglioriamo B a 3; passando per B arriviamo a D con costo 8.
Limite importante: questo ragionamento non vale in generale con pesi negativi.
2. Prim: far crescere un albero
Si sceglie un nodo di partenza. A ogni passo si prende l’arco meno pesante che collega un nodo già nell’albero a un nodo ancora esterno. Così il gruppo collegato cresce senza formare cicli, finché contiene tutti i nodi. Prim guarda sempre il confine dell’albero corrente: la scelta dipende dalla rete già costruita.
3. Kruskal: ordinare gli archi, evitare cicli
Si ordinano tutti gli archi dal più leggero al più pesante. Un arco viene accettato se collega due gruppi prima separati; viene scartato se chiuderebbe un ciclo. I gruppi si fondono progressivamente in un solo albero. Prim e Kruskal possono scegliere archi diversi quando esistono pari merito, ma il peso totale minimo coincide.
Prova sullo stesso grafo
Nel laboratorio interattivo dei grafi pesati puoi generare un grafo casuale connesso con 20–100 nodi e pesi interi da 1 a 20. Il seme riproduce il medesimo grafo; scegli partenza e meta per Dijkstra, poi confronta Prim e Kruskal sulla stessa rete. Avanza un passo alla volta o avvia l’animazione. Il disegno colloca i nodi nello spazio per leggibilità, ma la lunghezza visiva degli archi non è il loro peso.
Che cosa confrontare
Per Dijkstra osserva quando una distanza provvisoria migliora e quando diventa definitiva. Per Prim e Kruskal osserva il peso totale finale: deve coincidere anche se l’ordine delle scelte è diverso. Su un grafo grande puoi nascondere i numeri dei pesi per vedere meglio la struttura; il peso dell’arco esaminato resta visibile.