Cammini minimi: algoritmo di Dijkstra

Questa lezione ha come obiettivo l'implementazione dell'algoritmo di Dijkstra per trovare l'albero dei cammini minimi a partire da una sorgente.

Seguire i seguenti passi implementativi:

1. Leggere, se necessario, lo pseudocodice spiegato nel corso di teoria.
2. Creare una classe Dijkstra che usa le classi di sopra con i seguenti campi:
   • public static int[] pi: un vettore tale che pi[i] registra il padre del nodo i;
   • public static int[] cost: un vettore tale che cost[i] registra il costo dell'arco (pi[i], i), oppure 0 se l'arco non esiste;
   • public static int[] dist: un vettore che contiene le distanze dalla radice;
   • public static int root: il nodo radice dell'albero dei cammini minimi;
   e i seguenti metodi:
   • public static void dijkstra(Graph g, int root). Determina l'albero dei cammini minimi con radice root e lo salva nella variabile pi;
   • public static void printTree(). Stampa l'albero dei cammini minimi contenuto in pi;
   • public static void vizTree(). Salva in formato GraphViz il grafo originario in cui gli archi dell'albero dei cammini minimi sono evidenziati con il colore rosso e i nodi sono etichettati con le distanze dalla radice.
   • public static void printPath(int v). Stampa il cammino minimo dalla radice dell'albero a v e il suo costo.

Nota

Si usi la classe Graph per rappresentare il grafo e la classe MinHeap per implementare la coda con prioritą basata sul minimo Q come fatto nell'implementazione di Prim.