#include "bellman.h"

/*******************  fonction algoBellman  *******
    Lorsque l'on appelle cette fonction, on suppose que le graphe 
  ne possède pas de circuit. Si cette condition n'est pas 
  vérifiée, la fonction ne fonctionnera pas correctement.
  L'argument r indiqué en paramètre est le nom d'un sommet à partir
  duquel on cherche à calculer une arborescence de plus courts chemins.
  L'argument num contient au moment de l'appel une numérotation 
  topologique, les numéros topologiques étant compris ici entre 0 
  et ordre - 1.
  On suppose qu'au moment de l'appel de la fonction, une 
  allocation mémoire a déjà été faite pour les tableaux distance
  et antecedent. Il s'agit de deux tableaux pouvant contenir 
  chacun "ordre" int.
  La fonction algoBellman remplit les tableaux distance
  et antecedent. À la fin de l'algorithme :
  - pour un sommet x non accessible à partir de r, distance[x] vaut
  INFINI (défini plus haut par un #define) et antecedent[x] vaut -1.
  - l'antecedent de r vaut -1.
  - pour un sommet x accessible à partir de r et autre que r, 
  antecedent[x] est l'avant-dernier sommet dans un plus court 
  chemin de r à x et distance[x] est la distance de r à x. 
*/
void algoBellman(int depart)
{
  int sommet;
  int numero;
  int sommetMin;
  int min;
  PERE * adrPere;
  int unPere;
   
  for (sommet = 0; sommet < ordre; sommet++) 
    {
      antecedent[sommet] = -1;
      distance[sommet] = INFINI;
    }
  distance[depart] = 0;
  for (numero = num[depart] + 1; numero < ordre; numero++)
    {
      sommet = deNum[numero];
      min = INFINI;
      adrPere = graphe[sommet];
      while(adrPere != NULL)
	{
	  unPere = adrPere->nomPere;
	  if ((distance[unPere] != INFINI) && 
	      (distance[unPere] + adrPere->longueur < min))
	    {
	      min = distance[unPere] + adrPere->longueur;
	      sommetMin  = unPere;
	    }
	  adrPere = adrPere->suivant;
	}
      if (min < INFINI)
	{
	  distance[sommet] = min;
	  antecedent[sommet] = sommetMin;
	}
    } 
  free(deNum);
  /* Les deux instructions qui suivent ne sont utiles que 
     pour la période de tests */
  printf("Voici les antecedents trouves\n");
  ecrireValeurs(antecedent);
}