#include <stdio.h>
#include <unistd.h>
#include <limits.h>



/* Definition de l'operateur MIN  */
#ifndef  MIN
#define MIN(a, b)  (((a) < (b)) ? (a) : (b))
#endif


/* Nombre de sommets du graphe */
#define NB_SOMMETS 5


/* Valeur utilisee dans la matrice d'adjacence quand il
   n'existe pas d'arc entre deux sommets */
#define INFINI   USHRT_MAX


/* Une matrice est un tableau a 2 dimensions */
typedef int Matrice [NB_SOMMETS][NB_SOMMETS];




/* Matrice d'adjacence du graphe  */
Matrice graphe  = {
	{0, 	 1, 	   1,  INFINI    , 1},
	{INFINI,0, INFINI       ,1,	    1},
	{INFINI,1,	   0,  INFINI    , INFINI},
	{1,INFINI	 ,  1,     0,  INFINI     },
	{INFINI,INFINI,INFINI  ,1,       0},
	};


/* Matrice contenant, au final, les plus courts chemins */
Matrice Resultat;	

/* Variable temporaire utilisee pendant le calcul */ 
Matrice temp;


/* Effectue une partie du calcul */
void calcul_une_ligne(int i);

/* Affiche une matrice */
void matrice_affiche(Matrice mat);

/* Initialise la matrice dest avec le contenu de src */
void matrice_copie(Matrice dest, Matrice src);

/* Initialise une matrice avec un scalaire */
void matrice_init(Matrice dest, int val);




int main(int argc, char * argv[])
{
	int m,i;
	int diag;

	matrice_copie(Resultat,graphe);
	matrice_init(temp,0);


	printf("Matrice d'adjacence :\n");
	matrice_affiche(Resultat);
	
	for(m=2;m<=NB_SOMMETS-1;m++)
		{
		for(i=0;i<NB_SOMMETS;i++)
			calcul_une_ligne(i);

		matrice_copie(Resultat,temp);
                printf("Une iteration de faite...\n");

		}

	printf("\n\nPlus courts chemins pour tout point :\n");
	matrice_affiche(Resultat);

	exit(0);
}



void calcul_une_ligne(int i)
{
	int j,k;

	printf("Je calcule une ligne ....\n");

	for(j=0;j<NB_SOMMETS;j++)
		{
		temp[i][j]=INFINI;
		for(k=0;k<NB_SOMMETS;k++)
			temp[i][j]=MIN(temp[i][j],Resultat[i][k]+graphe[k][j]);
		}
}


void matrice_affiche(Matrice mat)
{
	int i,j;

	for(i=0;i<NB_SOMMETS;i++)
		{
		for(j=0;j<NB_SOMMETS;j++)
			if(mat[i][j]==INFINI)
				printf("+inf\t");
			else	printf("%d\t",mat[i][j]);
		printf("\n");
		}
	printf("\n");
	printf("\n");
}


void matrice_init(Matrice dest, int val)
{
	int i,j;

	for(i=0;i<NB_SOMMETS;i++)
		for(j=0;j<NB_SOMMETS;j++)
			dest[i][j]=val;
}


void matrice_copie(Matrice dest, Matrice src)
{
	int i,j;

	for(i=0;i<NB_SOMMETS;i++)
		for(j=0;j<NB_SOMMETS;j++)
			dest[i][j]=src[i][j];
}