Algorithme de djikstra

Télécharger le projet
Commenter

Description

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
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (mohtouati)