/*
 * 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 BellmanFord {
    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][2];

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

        // Utilizzo del booleano e del do-while secondo la regola di Bellman-Ford
        boolean procedi = true;

        do {
            procedi = false;
            for (int n = 0; n < nNodi; n++) {

                // 1. Se il nodo ha costo infinito, salto
                if (risultato[n][1] == Integer.MAX_VALUE)
                    continue;

                int nodoAttuale = n;
                int costoIniziale = risultato[nodoAttuale][1];

                // 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))
                        continue;

                    int temp = costoIniziale + matrice[nodoAttuale][r];
                    if (temp < risultato[r][1]) {
                        procedi = true;
                        risultato[r][1] = temp;
                        predecessori.get(r).clear();
                        predecessori.get(r).add(nodoAttuale);

                    } else if (temp == risultato[r][1]) {
                        // Considera altri predecessori
                        if (predecessori.get(r).contains(nodoAttuale))
                            continue;
                        if (risultato[r][0] != nodoAttuale) {
                            procedi = true;
                            predecessori.get(r).add(nodoAttuale);
                        }

                    }
                }
            }

        } while (procedi);

        // Stampa del risultato e salvataggio negli appunti

    }
}