Sujet Précédent Sujet Suivant

Bellman

perace Messages postés 9 Date d'inscription dimanche 16 mai 2010 Statut Membre Dernière intervention 23 mars 2010 - 23 sept. 2008 à 15:01
perace Messages postés 9 Date d'inscription dimanche 16 mai 2010 Statut Membre Dernière intervention 23 mars 2010 - 10 mai 2010 à 21:40
Qui d'autre que moi propose en C un algorithme de bellman qui en plus de la valeur
du chemin minimal donne aussi les points?!

5 réponses

Réponse 1 / 5
ctx_man Messages postés 285 Date d'inscription mardi 28 décembre 2004 Statut Membre Dernière intervention 20 janvier 2013 3
23 sept. 2008 à 18:01
Salut

Tu aurais pu mettre ton algo de Bellman ici en prime, histoire qu'on puisse se baser dessus.

Pour avoir les points suffit des les stocker dans un tableau quand tu passes dessus.


Le travail c'est la santé, ne rien faire c'est la préserver !!!
0
Réponse 2 / 5
SebLinck Messages postés 212 Date d'inscription mardi 17 mai 2005 Statut Membre Dernière intervention 23 juin 2011
30 sept. 2008 à 12:02
Salut,

sur Wikipedia:

booléen Bellman_Ford( G, s)

initialisation ( G, s) // les poids de tous les sommets sont mis à +infini
// le poids du sommet initial à 0
pour i=1 jusqu'à Nombre de sommets -1 faire
| pour chaque arc (u, v) du graphe faire
| | paux := poids(u) + poids(arc(u, v));
| | si paux < poids(v) alors
| | | pred(v) := u;
| | | poids(v) := paux;
pour chaque arc (u, v) du graphe faire
| si poids(u) + poids(arc(u, v))

Cordialement,
Sébastien.
0
Réponse 3 / 5
perace Messages postés 9 Date d'inscription dimanche 16 mai 2010 Statut Membre Dernière intervention 23 mars 2010
30 sept. 2008 à 15:22
merci
j'aimerai bien savoir comment vous comptez stocker les points dans un tableau quand vous y passer?
moi j'y ai passé une nuit blanche et c'est ce que j'ai pensé avant de commener le code
je veux bien envoyer mon code mais je me dis tjrs que la culture informatique commence par la recherche.
encore deux jours et j'envoie le code
0
Réponse 4 / 5
affaf09 Messages postés 2 Date d'inscription samedi 2 janvier 2010 Statut Membre Dernière intervention 4 avril 2011
13 mars 2010 à 22:29
salut je veut l'algourithme de bellman lmplémenter en java parce que j'ai trouvé bcp d'érreur et j pas pu les corrigé
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 5
perace Messages postés 9 Date d'inscription dimanche 16 mai 2010 Statut Membre Dernière intervention 23 mars 2010
10 mai 2010 à 21:40
deux jours qui sont très rapidement devenus deux ans!!! je suis désolée! j'espère que le code vous servira et aussi qu'il sera amélioré (j'étais encore debutant il y a deux ans et là je fais plus du C...)!!
j'espère trouver le temps de le commenter très prochainement... 
# 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=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;
 }


Bonne lecture!!
0

Discussions similaires

l'algorithme de routage de Bellman-ford
elabdelkhalki -
NHenry -

1 réponse
Rejoignez-nous