/*Le but de cet exercice est de completer le programme ci-dessous qui implemente
l'algorithme de Dijkstra. Cet algorithme calcule les plus courts chemins d'un sommet
d'un graphe oriente, appele racine, a tous les autres sommets. Il ne s'applique que
dans les cas ou toutes les valuations sont positives.
	Il peut etre decrit de la maniere suivante :
- on utilise trois tableaux :
		Le premier, indice par les sommets, contient des valeurs numeriques de meme type
	que les distances portees par les arcs du graphe. Nous l'appelerons ici "distance."
	A la fin de l'algorithme, si x est un sommet, distance[x] donne la distance de la
	racine a x. Au debut de l'algorithme, on initialise distance[racine] a 0 et les autres
	composantes du tableau distance a une valeur plus grande que toutes les longueurs de chemins
	que l'on peut avoir dans le graphe ; nous notons ci-dessous "infini" cette "grande valeur" .
		Le second, indice par les dommets sauf la racine, contient des noms de sommets. Ce
	tableau sert a indiquer, a la fin de l'algorithme, l'arborescence des plus courts
	chemins. On initialise touses ses composantes a -1. On appellera "arbo" ce tableau.A la
	fin de l'algoritme, x etant un sommet autre que la racine :
			si arbo[x]=-1, c'est qu'il n'existe aucun chemin de la racine a x.
			sinon, arbo[x] contient le "pere" de x dans l'arborescence des plus courts chemins
			depuis x que l'on aura determinee.
		Le troisieme, indice par les sommets, indique si un sommet appartient deja a
	l'arborescence des plus courts chemins en cours de construction. Toutes les
	composantes de ce tableau sont initialisees a 0. Ce tableau sera note "appartient".

	On note "ordre" l'ordre du graphe. Apres l'initialisation, on effectue une boucle dont on sort
au plus tard apres (ordre-1) iterations mais aussi si aucun sommet hors de l'arborescence des plus
courts chemins deja construite n'est atteignable par un chemin venant de la racine.
	Chaque iteration de la boucle consiste en :
	  - la recherche d'un sommet qui sera appele "pivot". Ce sommet est le sommet non encore
	  dans l'arborescencqui possede la plus petite valeur dans le tableau distance (ou l'un de tels
	  sommets s'ils sont plusieurs).
	  - si la recherche ci-dessus a conduit a un sommet "pivot" tel que distance[pivot]< infini,
			- on met ce sommet dans l'arborescence (c'est-a-dire qu'on donne la valeur 1 a
			appartient[pivot])
			- on actualise les composantes des tableaux distance et arbo pour les sommets non encore
	  dans l'arborescence de facon a ce que, pour un tel smmet y :
			distance[y]=minimum{distance[x]+longueur(arc(x,y)), ce minimum etant pris sur tous les
					sommets x appartenant deja a l'arborescence des plus courts chemins en cours de
					construction (il suffit de comparer la precedente valeur de distance[y] avec
					distance[pivot]+longueur(arc(pivot,y))pour savoir si l'ancienne valeur doit etre
					modifiee.
			arbo[y]=sommet qui atteint le minimum dans l'expression definissant distance[y].

Dans notre programme :
	- les sommets sont appeles 0, 1, ..., ordre-1
	- les distances sont des "float"
	- le graphe est code par le tableau des listes des fils des sommets, chaque fils etant accompagne
	de la longueur (notee poids) de l'arc correspondeant 
	- infini est choisie comme etant FLT_MAX, le plus grand "float".
	- le calcul de l'arborescence des plus courts chemins est mene par la fonction CalculArbo
qui appelle ChoixPivot et MiseAJour.
			- ChoixPivot recherche et retourne le sommet non encore dans l'arborescence qui possede
			la plus petite valeur de distance ; si ce minimum est FLT_MAX, la fonction ChoixPivot
			retourne -1.
			- MiseAJour est appelee juste apres avoir ajoute "pivot" a l'arborescence. Elle met a jour les
			champs du tableau distance correspondant au fils de "pivot" non encore dans l'arborescence.

LE TRAVAIL CONSISTE A COMPLETER LES FONCTIONS ChoixPivot ET CalculArbo

	*/
#include <stdio.h>
#include <float.h>
#include <stdlib.h>

typedef struct sommet
{
	int fils;
	float poids;
	struct sommet *suivant;
} Sommet;

typedef Sommet *Arc;

void EmplirGraphe(Arc *, int);
void CalculArbo(Arc *, int, int, int *);
int ChoixPivot(int,int *,float *);
void MiseAJour(Arc *, int ,int *,float *,int, int *);

void AfficheArbo(int, int, int *);

int main()
{
	int racine,ordre;
	Arc *graphe;
	int *arbo; /*tableau donnant les peres de chaque sommet dans l'arborescence
						des plus courts chemins*/

	printf("donner l'ordre du graphe : ");
	scanf("%d",&ordre);
	graphe=(Arc *)malloc(ordre*sizeof(Arc));
	EmplirGraphe(graphe,ordre);
	printf("quel est le point d'ou l'on calcule les distances : ");
	scanf("%d",&racine);
	arbo=(int *)malloc(ordre*sizeof(int));
	CalculArbo(graphe, ordre, racine ,arbo);
	AfficheArbo(ordre,racine,arbo);
   return 0;
}

void EmplirGraphe(Arc *graphe,int ordre)
{
	int i;
	Arc p;

	for(i=0;i<ordre;++i) graphe[i]=NULL;
	printf("donner le numero de l'origine, puis le numero "
	"de l'extremite,\n puis le poids de chaque arc, terminer la "
	"saisie par -1\n");
	scanf("%d",&i);
	while (i!=-1)
	{
		p=(Arc)malloc(sizeof(Sommet));
		scanf("%d",&p->fils);
		scanf("%f",&p->poids);
		p->suivant=graphe[i];
		graphe[i]=p; 
		scanf("%d",&i);
	}
}

void CalculArbo(Arc *graphe,int ordre, int racine, int *arbo)
{
	int i,pivot;
	float *distance;
	int *appartient; /*tableau indice par les sommets indiquant, en cours de calcul,
					si un sommet i donne appartient (sommet[i]=1) ou non (sommet[i]=0)
					a l'arborescence des plus courts en cours de construction*/
	/* allocations memoire et initialisations*/
	appartient=(int *)malloc(ordre*sizeof(int));
	distance=(float *)malloc(ordre*sizeof(float));
	for(i=0;i<ordre;++i)
	{
		distance[i]=FLT_MAX;
		appartient[i]=0;
		arbo[i]=-1;
	}
	distance[racine]=0;
	/*on construit l'arborescence des plus courts chemins*/
	for(i=1;i<ordre;++i)
	{
		pivot=ChoixPivot(ordre,appartient,distance);
		if (pivot==-1) return; /*les sommets hors de l'arborescence des plus courts
									 chemins depuis la racine, ne sont pas "atteignables"
									 par un chemin venant de la racine*/
		appartient[pivot]=1;
		MiseAJour(graphe,ordre,appartient,distance,pivot,arbo);
	}
	free (distance);
	free(appartient);
 }

int ChoixPivot(int ordre,int *appartient,float *distance)
{
	/*A COMPLETER */
}

void MiseAJour(Arc *graphe,int ordre,int *appartient,float *distance,int pivot,int *arbo)
{
	/*A COMPLETER */
}

void AfficheArbo(int ordre,int racine, int *arbo)
{
	int i;

	printf("\n");
	for (i=0;i<ordre;++i)
		if(i!=racine)
			if(arbo[i]==-1)printf("le sommet %d n'est pas dans l'arborescence\n",i);
			else printf("le pere dans l'arborescence du sommet %d est : %d\n",i,arbo[i]);
}