//AVTOR: Boštjan Kač 27005020 (druga seminarska naloga pri predmetu R2)

/*
 * LITERATURA:
 * http://en.wikipedia.org/wiki/Bellman-Ford_algorithm
 * http://www.cs.arizona.edu/classes/cs445/spring05/ShortestPath2.prn.pdf
 */

//RAZRED JE NAMENJEN ISKANJU NAJKRAJSIH POTI V UTEZENO USMERJENEM GRAFU PREKO BELLMAN-FORD ALGORITMA.
public class BellmanFord{
  
  //v ... vozlisca v1,v2,...,vn
  //e ... mnozice utezenih usmerjenih povezav e1,e2,...,em
  //s ... izhodniscno vozlisce
  public static int[][] resi(int [] v, Povezava [] e, int s)throws Exception{
    
    int n = v.length; //dolzina tabele v oz. stevilo vozlisc
    int m = e.length; //dolzina tabele e oz. stevilo utezenih usmerjenih povezav
    
    
    //korak 1:   
    int [] d = new int[n]; //dolzine najkrajsih poti od izhodiscnega vozlisca s do vozlisc v1,v2,...,vn
    int [] pi = new int[n]; //optimalni predhodniki (ocetje) vozlisc v1,v2,...,vn
    for(int i = 0; i < v.length; i++){
      if(v[i] == s){
        d[i] = 0;
      }
      else{
        d[i] = 999999; //nastavimo (zelo) veliko dolzino najkrajse poti (originalno infinity (neskončno) ... java ne pozna)    
      }
    }
    
    for(int i = 0; i < n; i++){
      pi[i] = -1; //nastavimo negativno vrednost (originalno nil ... java ne pozna)
    }
    
    //korak 2:
    int zacetekPovezave = 0; //zacetek povezave
    int konecPovezave = 0; //konec povezave
    int utezPovezave = 0; //utez na povezavi
    
    for(int j = 1; j <= n-1; j++){ //v najslabsem primeru (n-1)-krat ponovimo
      for(int i = 0; i < m; i++){ //gremo cez vse (utezene usmerjene) povezave
        zacetekPovezave = e[i].vrniZacetek(); 
        konecPovezave = e[i].vrniKonec(); 
        utezPovezave = e[i].vrniUtez(); 
      
        if(d[zacetekPovezave] + utezPovezave < d[konecPovezave]){
        d[konecPovezave] = d[zacetekPovezave] + utezPovezave;
        pi[konecPovezave] = v[zacetekPovezave]; //ali pi[konecPovezave] = zacetekPovezave
        }
        
      }
           
    } 
    
    //korak 3:
    //preverimo ali so v grafu G negativni cikli
    for(int i = 0; i < m; i++){
        zacetekPovezave = e[i].vrniZacetek(); 
        konecPovezave = e[i].vrniKonec(); 
        utezPovezave = e[i].vrniUtez();     
        if(d[zacetekPovezave] + utezPovezave < d[konecPovezave]) throw new Exception ("Graf vsebuje negativne cikle!");          
      }
    
    //izhodna matrika
    int [][] izhodna = new int [2][n];
    
    for(int i = 0; i < n; i++){
      izhodna[0][i] = d[i];
    }
    for(int i = 0; i < n; i++){
      izhodna[1][i] = pi[i];
    }
     
    return izhodna;
  }
  
  //metoda za izpis resitve (matrike)
  public static void izpisiResitev(int [][] mtr){
    for(int i = 0; i < mtr.length; i++){  
      for(int j = 0; j < mtr[i].length; j++){
        System.out.print(mtr[i][j] + " ");
      }
      System.out.println();
    }
  }
  
}

/* "Izjavljam, da sem nalogo opravil samostojno in da sem njen avtor. Zavedam se, da v primeru,
če izjava prvega stavka ni resnična, kršim disciplinska pravila Fakultete za matematiko in fiziko." */
