ALGORITHME DE DJIKSTRA

#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);
}

Télécharger le zip

22 juillet 2008 02:18:50 :

enlevé la capture

23 juillet 2008 13:10:33 :

prise en compte de quelque remarques