/*
**  fastAllPairsShortestPath.c
**
**  Implementazione di un algoritmo di programmazione dinamica per il 
**  calcolo del cammino di costo minimo tra ogni coppia di vertici di
**  un grafo G con pesi assegnati agli spigoli.
**
**  FastAllPairsShortestPath(G)
**    INPUT: Un grafo G orientato con pesi W(u,v) assegnati agli spigoli
**    OUTPUT: La matrice D dei costi dei cammini minimi per ciascuna coppia
**            di vertici in V(G)
**    per ogni i, j = 1, 2, ..., n:
**      se (i,j) e' uno spigolo di G allora L(1)(i,j) = W(i,j)
**      altrimenti L(1)(i,j) = infinito
**    fine-ciclo
**    k = 1
**    fintanto che k < n-1:
**      per i=1, 2, ..., n:
**        per j=1, 2, ..., n:
**          L(2k)(i,j) = infinito
**          per h=1, 2, ..., n:
**            L(2k)(i,j) = min{L(2k)(i,j), L(k)(i,h)+L(k)(h,j)}
**          fine-ciclo
**        fine-ciclo
**      fine-ciclo
**      k = 2k
**    fine-ciclo
**
**  #(@)20120430(liverani@mat.uniroma3.it)
*/

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include "grafi.h"

/*
 *  Funzione che implementa l'algoritmo FastAllPairsShortestPath
 */

void fastAllPairsShortestPath(grafoPesato G, int **D) {
  int ***L, i, j, k, h;
  /* allocazione dinamica della matrice L con 3 dimensioni */
  L = malloc(sizeof(int *)*(G.n+1));
  for (k=1; k<=2*G.n; k=k*2) {
    L[k] = malloc(sizeof(int *)*(G.n+1));
    for (i=1; i<=G.n; i++) {
      L[k][i] = malloc(sizeof(int)*(G.n+1));
    }
  }
  /* inizializzazione di L */
  for (i=1; i<=G.n; i++)
    for (j=1; j<=G.n; j++)
      L[1][i][j] = G.W[i][j];
  /* FastAllPairsShortestPath */
  k = 1;
  while (k < G.n-1) {
    for (i=1; i<=G.n; i++) {
      for (j=1; j<=G.n; j++) {
        L[2*k][i][j] = INFINITO;
        for (h=1; h<=G.n; h++) {
          if (L[2*k][i][j] > L[k][i][h]+L[k][h][j]) {
            L[2*k][i][j] = L[k][i][h]+L[k][h][j];
          }
        }
      }
    }
    k = 2*k;
  }
  /* copia L[k] in D */
  for (i=1; i<=G.n; i++)
    for (j=1; j<=G.n; j++) 
      D[i][j] = L[k/2][i][j];
  return;
}

/*
 *  funzione principale
 */

int main(void) {
  grafoPesato G;
  int **D, i, j;
  leggiGrafoPesato(&G);
  D = malloc((G.n+1)*sizeof(int *));
  for (i=1; i<=G.n; i++) 
    D[i] = malloc((G.n+1)*sizeof(int));
  fastAllPairsShortestPath(G, D);
  printf("Matrice dei costi minimi:\n");
  for (i=1; i<=G.n; i++) {
    for (j=1; j<=G.n; j++)
      if (D[i][j] < INFINITO)
        printf("%3d ", D[i][j]);
      else
        printf("INF ");
    printf("\n");
  }
  return(0);
}