/***************************** Floyd.java *************************************/

/** berechnet alle kuerzesten Wege und ihre Kosten mit Algorithmus von Floyd  */
/*  der Graph darf keine Kreise mit negativen Kosten haben                    */

public class Floyd {

  public static void floyd (int n,          // Dimension der Matrix
                            double [][] c,  // Adjazenzmatrix mit Kosten
                            double [][] d,  // errechnete Distanzmatrix
                            int    [][] p){ // errechnete Wegematrix 
    
    int i, j, k;                            // Laufvariablen
    for (i=0; i < n; i++) {                 // fuer jede Zeile
      for (j=0; j < n; j++) {               // fuer jede Spalte
        d[i][j] = c[i][j];                  // initialisiere mit Kantenkosten
        p[i][j] = i;                        // vorletzter Knoten 
      }                                     // vorhanden ist nun D hoch -1
    }

    for (k=0; k < n; k++) {                 // fuer jede Knotenobergrenze 
      for (i=0; i < n; i++) {               // fuer jede Zeile
        for (j=0; j < n; j++) {             // fuer jede Spalte
          if (d[i][k] + d[k][j] < d[i][j]){ // falls Verkuerzung moeglich
            d[i][j] = d[i][k] + d[k][j];    // notiere Verkuerzung
            p[i][j] = p[k][j];              // notiere vorletzten Knoten 
          }                                 // vorhanden ist nun D hoch k
        }
      }
    }
  }
}