#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 algoBellmanCourt()
{
  int sommet;
  int numero;
  int sommetMax;
  int max;
  PERE * adrPere;
  int unPere;
int depart;

  for (depart=tacheDepart;depart<derniereTache;depart++){

	 // printf("la valeur de la var depart est: %d\n",depart);
	  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];
      max = -INFINI;
      adrPere = graphe[sommet];
      while(adrPere != NULL)
	{
	  unPere = adrPere->nomPere;
	  if ((distance[unPere] != -INFINI) && 
	      (distance[unPere] + adrPere->longueur > max))
	    {
	      max = distance[unPere] + adrPere->longueur;
	      sommetMax  = unPere;
	    }
	  adrPere = adrPere->suivant;
	}
      if (max > -INFINI)
	{
	  distance[sommet] = max;
	  antecedent[sommet] = sommetMax;
	}
    } 
  //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);
  //system("PAUSE");
  afficherCourt(depart);
  }

printf("la date au plus tard pour la tache finale est : %d\n\n",dureeTotaleProjet);
tableauDatePlusTard[ordre-1] = dureeTotaleProjet;
  }