/*
 * Algoritmi di Routing
 * 
 * @author Francesco Mancuso
 * @version 1.3
 * @docs https://routing.francescomancuso.it
 * 
 */

package it.mancuso.mst.algoritmi;

import it.mancuso.mst.utils.Clipboard;
import java.util.ArrayList;
import java.util.List;

public class Dijkstra {
    public static void doIt(int nNodi, int matrice[][]) {

        // Utilizzo di un array di liste per memorizzare i predecessori
        List<List<Integer>> predecessori = new ArrayList<>();

        // Inizializziamo ogni nodo con una nuova lista vuota
        for (int i = 0; i < nNodi; i++) {
            predecessori.add(new ArrayList<>());
        }

        // Inizializziamo la matrice risultato
        int risultato[][] = new int[nNodi][3];

        for (int i = 0; i < nNodi; i++) {
            risultato[i][0] = i; // N Nodi
            risultato[i][1] = Integer.MAX_VALUE; // Costo
            risultato[i][2] = 0; // Esaminato
        }
        
        risultato[0][1] = 0; // Costo zero per il nodo 0
        predecessori.get(0).add(-1); // Nessun predecessore per il nodo 0

        for (int n = 0; n < nNodi; n++) {
            // Scorro ogni nodo
            int nodoAttuale = 0;

            // 1. Trovare il nodo con il costo minore e non esaminato
            int min = Integer.MAX_VALUE;
            for (int m = 0; m < nNodi; m++) {
                if ((min > risultato[m][1]) && (risultato[m][2] == 0)) {
                    min = risultato[m][1];
                    nodoAttuale = m;
                }
            }

            int costoIniziale = risultato[nodoAttuale][1];
            risultato[nodoAttuale][2] = 1; // Nodo esaminato

            // 2. Controlla tutti i valori dalla matrice e aggiornali se sono minori dei costi attuali
            for (int r = 0; r < nNodi; r++) {
                if ((matrice[nodoAttuale][r] == Integer.MAX_VALUE) || (risultato[r][2] != 0)) {
                    continue;
                }

                int temp = costoIniziale + matrice[nodoAttuale][r];
                if (temp < risultato[r][1]) {
                    risultato[r][1] = temp;
                    predecessori.get(r).clear();
                    predecessori.get(r).add(nodoAttuale);
                    
                } else if (temp == risultato[r][1]) {
                    // Considera altri predecessori
                    predecessori.get(r).add(nodoAttuale);
                }
            }
        }

        // Stampa del risultato e salvataggio negli appunti

    }
}