Bellman

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

void matrice(int t[][100], int n)
{  int i,j,v;
 printf(" Vous allez saisir les coefficients de la matrice d'adjacence du graphe.\n");
 printf("La saisie se fait ligne par ligne.\n");
 printf("Donnez la valeur 0 si l'arc cite n'est pas defini.\n");
 printf("\n");
 system ("PAUSE");
 for(i=0;i<n;i++)
 for (j=0;j<n;j++)
 {printf ("Donner la valeur de l'arc (%d,%d):\n",i,j);
   scanf ("%d",&(t[i][j]));
 }
 printf("\n");
  printf("Vous avez saisi la matrice ci-dessous:\n");
  for(i=0;i<n;i++)
 {for (j=0;j<n;j++)
   printf("%5d",t[i][j]);
   printf("\n");
 }
}



void predecesseur(int t[][100],int p[][100],int n) //fournit une matrice p[] tel que:
{ int i,j,k,cpt;
for (j=0;j<n;j++)// chaque ligne j(=un tableau) definit un sommet
  {k=1; cpt=0;
   printf("Les predecesseurs de %d sont gh:\n",j);
   for (i=0;i<n;i++)
      {if ( t[i][j]!=0)
      {p[j][k]=i;
      k++;
      cpt++;}
      p[j][0]=cpt;}//dans la premiere case de la ligne j, on met le nombre de ses predecesseurs;dans le reste on liste les predecesseurs
   for (i=1;i<=cpt;i++)
   printf("%5d",p[j][i]);
   printf("\n");
  }
}



int recherche(int t[],int n,int *p,int deb,int fin)//recherche (fin-deb+1) elements de p[] dans les n elements de t[] et renvoie le nombre d'elements trouves qui est 'trouve'
{int k, trouve,l,m;
trouve=0;
for (k=deb;k<=fin;k++)
{ l=0;m=0;
while((l==0)&&(m<n))
{if (t[m]==p[k])
 l=1;
 else
 m++;
}
trouve=trouve+l;
}
 return trouve;
}



int recher(int t[], int n,int el) //recherche 'el' dans les n elements de t[],renvoie 1 si 'el' est retrouve  et 0 sinon
 { int i;
 int trouve=0;
 for (i=0;i<n;i++)
  if (t[i]==el)
    trouve=1;
 return trouve;}



int ordinal(int p[][100],int n,int ord[])//ordonne les sommets par une fonction ordinale en les rangeant dans ord[]
{int k, i,j,f;
k=0;
 for (j=0;j<n;j++)  //range d'abord ceux qui n'ont pas de predecesseurs;il doit y en avoir un et un seul
 {if (p[j][0]==0)
    {ord[k]=j;
     k++;}
 }
if (k==0)
printf("Il n'y a pas de sommet racine\n");

if (k>1)
{printf("Il y a plus d'une racine\n");
return -1;
}
if (k==1)
 {for(i=0;i<n;i++)
    for (j=0;j<n;j++)
      if(recherche(ord,k,p[j],1,p[j][0])==p[j][0])//verifie si pour un sommet 'j' donne tous les predecesseurs sont dans ord[]
           if (recher(ord,k,j)==0)//s'il n'est pas encore dans ord[], l'y mettre
            {ord[k]=j;
             k++;
             }

 }

if (k==n)
  {printf("La numerotation par une fonction ordinale donne:\n");
  for (i=0;i<k;i++)
   printf("%5d",ord[i]);
   printf("\n");
   return k;}//retourne le nombre de sommets effectivement ordonnes
 if (k<n)
 {printf("Le graphe contient un circuit\n");//si tous les sommets ne sont pas dans ord[], c'est parce que nous avons un circuit
  return -1;} //retourne -1 s'il n'y a pas une unique racine
}


void MinIndice(int t[],int n, int*min,int*ind)//recherce le minimum des elements non nuls de t[](de taille n) et fournit son indice 'ind' et sa valeur 'min'
{int i;
*min=0;
*ind=0;
for(i=0;i<n;i++)
  if(t[i]!=0)
  { if(*min==0)
      {*min=t[i];
      *ind=i;}
    else
       if(*min>t[i])
        {*min=t[i];
       *ind=i;}
  }
}


void bellman(int pred[][100], int ord[], int t[][100],int n)
{int v[100][100]; int ch[100];
int i,j,a,b,last,z,k;
int *h;
v[0][0]=0;
  for (i=1;i<n;i++)
  for (j=0;j<i;j++)
   {MinIndice(v[j],i,&a,&b);
    h=&(pred[ord[i]][1]);
    v[i][j]=recher(h,pred[ord[i]][0],ord[j])*a+ t[ord[j]][ord[i]];
   }
MinIndice(v[n-1],n,&a,&b);
printf("La valeur du chemin le plus court est: %d\n",a);
 ch[0]=ord[n-1];
z=1;
while (b!=0)
{
ch[z]=ord[b];
last=b;
z++;
MinIndice(v[last],last+1,&a,&b);
}

printf("le chemin le plus court est:\n");
for (k=z;k>=0;k--)
printf("%5d",ch[k]);
}

int main()
{ int t[100][100]; int p[100][100];int ord[100];
 int n; int a; int b;
 printf ("Donner le nombre de sommets...\n");
 scanf("%d",&n);
 matrice(t,n);
 predecesseur(t,p,n);
 if (ordinal(p,n,ord)==n)
   bellman(p,ord,t,n);
 printf("\n");
 system("PAUSE");
 return 0;
 }