ce programme est un tp de recherche operationnelle implemente le l'algorthme de Djikstra
Source / Exemple :
#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
#include <time.h>
int n;
int t[20][20],p[20],arc[20][20],a[20],s[20],q,j,i,r,o,z,x;
long c;
int main()
{
time_t ti;
printf(" ===========================================================\n");
printf(" UNIVERSITE DE BEJAIA\n ");
printf(" DEPARTEMENT D'INFORMATIQUE \n ");
printf(" ETUDIANT : TOUATI MOHAMED \n ");
printf(" MODLE DE RECHERCHE OPERATIONNELLE\n");
printf(" ===========================================================\n");
printf(" ***bonjour***\n\n");
printf(" Algorithme de Djikstra :\n\n\n");
getch();
int clrscr();
printf(" ===========================================================\n");
printf(" UNIVERSITE DE BEJAIA\n ");
printf(" DEPARTEMENT D'INFORMATIQUE \n ");
printf(" ETUDIANT : TOUATI MOHAMED \n ");
printf(" MODULE DE RECHERCHE OPERATIONNELLE\n");
printf(" ===========================================================\n\n");
printf("introduire le nombre de sommet n \n\n");
printf("n=");
scanf("%d",&n);
a:
printf(" pour avoir la matrice manualement tappez '1' \n\n");
printf(" pour avoir la mtrice automatiquement tappez '2' \n");
scanf("%d",&q);
if(q!=1 && q!=2)
{
goto a;
}
if (q==1)
{
printf(" donnez maintenant les valeurs de la matrice:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
ref:
printf("X(%d,%d)=",i,j);
scanf("%d",&t[i][j]);
if (t[i][j]<0)
{
printf("error!!!\a\n");
printf("reffere l'introduction de la valeure de X(%d,%d)>=0\n",i,j);
goto ref;
}
}
}
}
else
{
srand((unsigned) time(&ti));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
t[i][j]=(rand() % 10);
printf(" %d ",t[i][j]);
}
printf("\n\n\n");
}
}
getch();
for(i=1;i<=n;i++)
t[i][i]=0; ///pour eliminer les boucles
printf("---------------------------------------------------\n\n");
//clrscr();
for(i=1;i<=2;i++)
for(j=1;j<=2;j++) //initialisation de arc
arc[i][j]=0;
for(i=1;i<=n;i++) // initialiser les potenciels a l'infinit
p[i]=1000;
for(i=1;i<=n;i++)
a[i]=0;
for(i=1;i<=n;i++)
s[i]=0;
o=1; /// "o"la variable qui contien la racine
x=1;
zero:
if(o<=n)
{
s[x]=1;
p[x]=0;
z=1;
un:
for(i=1;i<=n;i++)
{
if((s[i]==0)&&(t[x][i]!=0))
{
if((p[x]+t[x][i])<p[i])
{
p[i]=p[x]+t[x][i];
a[i]=x; //extremité initiale "x" extremité terminale "i"
}
}
}
deux:
for(i=1;i<=n;i++)
{
if(s[i]==0)
{
z=i; //z est un sommet qui n'appartin pas a S
i=n;
}
}
for(i=1;i<=n;i++)
{
if((s[i]==0)&&(p[i]<p[z]))
{z=i;} //z est un sommet qui n'appartin pas a S mais de ptentieile minimume
}
if(p[z]==1000) ////si le ptontiel min est a l'infinit
{ ////n'est pas une racine
for(i=1;i<=2;i++)
for(j=1;j<=2;j++)
arc[i][j]=0;
for(i=1;i<=n;i++)
p[i]=1000;
for(i=1;i<=n;i++)
a[i]=0;
for(i=1;i<=n;i++)
s[i]=0;
o=o+1;
x=o;
goto zero;
}
else
{
s[z]=1; ///introduire l'arc (a[z],z) dans l'arborecence
arc[(a[z])][z]=t[(a[z])][z];
x=z;
}
for(i=1;i<=n;i++)
{
if(s[i]==0)
{goto un;}
}
}
printf("l'arborecence de poid minimume avec la racine le sommet %d est:",o);
printf("\n\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %d ",arc[i][j]);
}
printf("\n\n\n");
}
printf("\n\n\n");
printf("la racine est: %d",o);
}
Conclusion :
universté de bejaia
j'ai créé ce code ya deux ans pour mon tp de recherche operationnelle Djikstra -ford merci pour les remarques je prendrai en copte a la venire
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.