/*
        On choisit un sommet r comme point de depart.
	L'algorithme de Dijkstra 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[r] 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 r, contient des 
noms de sommets. Ce tableau sert a indiquer, a la fin de l'algorithme, 
l'arborescence des plus courts chemins. On initialise toutes ses composantes 
a -1 sauf celle de r qui est initialisee a -2. On appellera "antecedent" ce 
tableau.A la fin de l'algoritme, x etant un sommet autre que r :
   si antecedent[x]=-1, c'est qu'il n'existe aucun chemin de la racine a x.
   sinon, antecedent[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 "n" 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'arborescence qui 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 antecedent 
                pour les sommets non encore dans l'arborescence de facon a ce que, 
                pour un tel sommet 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.
                   antecedent[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 son ordre et le tableau des listes des fils 
	  des sommets, chaque fils etant accompagne de la longueur (notee longueur) 
          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 calcule_arbo 
*/


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

#define INFINI FLT_MAX
struct fils
{
	int nom;
	float longueur;
	struct fils *suivant;
};

typedef struct fils * p_Fils;

typedef struct graphe 
{
  int n;
  p_Fils * table;
}Graphe;

Graphe lire_fichier(char *);
void calcule_arbo(Graphe, int, int *, float *);
void affiche(int, int *, float *);
void verifier_graphe(Graphe);

int main(int argc, char ** argv)
{
	int r;
	Graphe graphe;
	int * antecedent; /*tableau donnant les peres de chaque sommet 
			    dans l'arborescence des plus courts chemins*/
	float * distance;

	graphe = lire_fichier(argv[1]);
	verifier_graphe(graphe);
	r = atoi(argv[2]);
	antecedent = (int *)malloc(graphe.n * sizeof(int));
	distance  = (float *)malloc(graphe.n * sizeof(float));
	calcule_arbo(graphe, r, antecedent, distance);
	affiche(graphe.n, antecedent, distance);             
	return 0;
}

Graphe lire_fichier(char * nom_fichier)
{
  int i;
  p_Fils p;
  FILE * fichier;
  int or, extr;
  float longueur;
  Graphe graphe;
  
  fichier = fopen(nom_fichier, "r");
  if (fichier == NULL)
    {
      printf("fichier inexistant\n");
      exit(1);
    }
  fscanf(fichier, "%d", &(graphe.n));
  graphe.table =(p_Fils *)malloc(graphe.n * sizeof(p_Fils));
  for(i = 0;i < graphe.n; ++i) graphe.table[i] = NULL;
  while (!feof(fichier))
    {
      p = (p_Fils) malloc(sizeof(struct fils));
      fscanf(fichier, "%d%d%f",&or, &extr, &longueur);
      p -> nom = extr;
      p -> longueur = longueur;
      p->suivant = graphe.table[or];
      graphe.table[or] = p; 
    }
  return graphe;
}
  /* DIJKSTRA EN SUPPOSANT QUE r EST RACINE DU GRAPHE
     on gere un ensemble S de sommets (grace a un tableau contenant 0 ou 1 
     selon l'appartenance a S d'un sommet).
     Au depart:
     toutes les valeurs de dist valent lINFINI sauf dist[r] qui vaut 0
     tous les ant valent -1 sauf ant[r] qui vaut -2 
     sauf ant[r] qui vaut -2 et dist[r] qui vaut 0.
     Puis, on repete n - 1 fois (n = ordre du graphe0 
     - rechercher le sommet non dans S ayant la plus petite valeur de dist ; 
     l'appeler pivot ;
     - mettre pivot dans S ;
     - parcourir les fils de pivot non dans S pour actualiser dist et ant :
          si dist(pivot) + longueur(arc(pivot, y)) < dist(y)
	         dist(y) <- dist(pivot) + longueur(arc(pivot, y));
		 ant(y) <- pivot;
  */
void calcule_arbo(Graphe graphe, int r, int * ant, float * dist)
{
  int i, j, pivot, un_fils;
  float dist_min;
  p_Fils p;
  int fini = 0;

  int * appartient; /*tableau indice par les sommets indiquant, en cours de 
		     calcul, si un sommet i donne appartient (fils[i]=1) 
		     ou non (fils[i]=0)a l'arborescence des plus courts 
		     en cours de construction*/

  /* allocation memoire et initialisations*/

  appartient = (int *) malloc(graphe.n * sizeof(int));
  for(i = 0;i < graphe.n; ++i)
    {
      dist[i] = INFINI;
      appartient[i] = 0;
      ant[i] = -1;
    }
  ant[r] = -2;
  dist[r] = 0;

  /*on construit l'arborescence des plus courts chemins*/
  for(i = 0;i < graphe.n - 1; ++i)
    {
      // on cherche le pivot
      pivot = -1;
      dist_min = INFINI;
      for(j = 0; j < graphe.n; ++j) 
	if ((!appartient[j]) && (dist[j] < dist_min))
	  {
	    dist_min = dist[j];
	    pivot = j;	    
	  }
      if (dist_min == INFINI) break;
      appartient[pivot] = 1;
      
      p = graphe.table[pivot];
      
      // on actualise dist et ant
      while(p != NULL)
	{
	  un_fils = p -> nom;
	  if (!appartient[un_fils])
	    if (dist[pivot] + p -> longueur < dist[un_fils] )
	      {
		dist[un_fils] = dist[pivot] + p -> longueur;
		ant[un_fils] = pivot;
	      }
	  p = p->suivant;
	}
    }
  free(appartient);
}

void affiche(int n, int * ant,float * distance)
{ 
  int i;
  
  for (i = 0; i < n; ++i)
    {
      if(ant[i] == -1)printf("le sommet %d ne peut pas etre atteint\n",i);
      else if (ant[i] == -2)printf("le sommet %d est la racine\n", i);
      else printf("l'antecedent dans l'arborescence du sommet %d est %d"
		  " et la distance est %.2f\n",i,ant[i], distance[i]);
    }
}

void verifier_graphe(Graphe graphe)
{
  int i;
  p_Fils p;

  for (i = 0; i < graphe.n; i++)
    {
      p = graphe.table[i];
      printf("voisins de %d : ", i);
      while (p != NULL) 
	{
	  printf("%d, %.2f;  ", p -> nom, p -> longueur);
	  p = p -> suivant;
	}
      printf("\n");
    }
}