Algorithme de djikstra

Soyez le premier à donner votre avis sur cette source.

Vue 10 599 fois - Téléchargée 504 fois

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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
11
Date d'inscription
mardi 24 février 2004
Statut
Membre
Dernière intervention
20 septembre 2008

slt,
je voudrais te demander si l'algorithme de djikstra tient compte des cycles possibles dans les suites d'arcs à 2 sommets en cycles multiples co-cycliques ou non ?
parce que je suis en train de présenter la résolution totale de matrices quelconques quelquesoit les fonctionneles ou équations indéterminées présentes; en rapport avec la résolution de nombreux problèmes dont notamment le jeu d'échecs! et je développe présentement ! un algorithme et un code source pour le calcul de toutes les positions au jeu d'échecs en tenant compte des matrices et non de l'allocation dynamique contiguë de mémoire qui de ce fait de contigüité n'est pas optimale étant entendu que la mémoire allouable max pour un processus reste équivalente !!!!! de plus ! l'aspect visuel directement représentable des matrices permet plus facilement de déterminer les commutativités, asymétries, cycles ou itérations redondantes plus aisément !!!!! surtout lorque l'on est en mode manuel !!!!! avec retour de la commande shell au programmeur pour décision litigieuse !!!!! à résoudre !!!!!
confère mes pages à ootbtdkg2 pour plus d'infos !!!!!
cordialement,
considérations,
didkac
Messages postés
173
Date d'inscription
jeudi 20 décembre 2001
Statut
Membre
Dernière intervention
22 août 2008

Brunews:
On s'en fout un peu du cycle perdu, c'est vraiment pas dans une portion critique du code.
Par contre du code chiant à lire, je trouve ca plus critique.
C'est vrai que quelque chose comme
if (q==1) // traitement 1
else if (q==2) // traitement 2
else {
printf/scanf
}
aurait été un poil meilleur, mais bon l'idée c'était surtout de pas écrire de goto la ou un if/else aurait suffit..

Mais je connais ton opinion la dessus, pas la peine de continuer le débat sur un sujet ou chacun à des arguments ...
Messages postés
3212
Date d'inscription
lundi 7 novembre 2005
Statut
Membre
Dernière intervention
16 février 2009
12
scanf("%d", &n) ne peut qu'accepter un nombre. Si ce n'est pas un nombre, la valeur de n avant l'appel sera conservé.
Suffit donc d'initialiser n à -1 par exemple. Ça ne passera pas le test des bornes et un nouveau nombre sera redemandé, si dans une boucle.
Toujours aucun besoin de test supplémentaire.
Maintenant, si l'utilisateur entre une chaine comme suit: 12%?231, seul les premiers caractères seront prit. Si on tien compte de ce cas, un test sur l'ensemble de la chaine peut devoir s'appliquer. Cependant, sur un projet relativement modeste ou spécialisé (qui n'a pas à traiter ce genre de chose), ce genre de test n'est pas très important, car, de toute façon, si le nombre créé par les premiers caractères dépasse les bornes, ça ne passera toujours pas le test donc aucun débordement tampon possible (résultat (peut-être) faussé cependant).

Ensuite, un caractère, quel qu'il soit vaut toujours une valeur numérique/hexadécimal étant donnée que c'est ce qu'il est. Entre '*' 'a' '$' ou ce que tu veux à la saisie, tu pourras toujours l'utiliser en tant que valeur numérique.
Coté ergonomique (pour l'utilisateur), je te l'accorde, ce n'est pas très chic mais coté logiciel, on s'en fout.
Messages postés
871
Date d'inscription
jeudi 6 juillet 2006
Statut
Membre
Dernière intervention
6 janvier 2012
1
oui t'a raison SAKingdom
si on met 0 ça donnera rien et si tu ne met pas un chiffre tu met un a ou * t'as essayé?
Messages postés
3212
Date d'inscription
lundi 7 novembre 2005
Statut
Membre
Dernière intervention
16 février 2009
12
"ne passera pas le test de confirmation"

Quand je parle du test de confirmation ici, je parle du test pour confirmer que le nombre entré est entre 0 et 19 (la représentation entière de 'a' étant 97, (menfin la représentation... ce que vaut réellement 'a') ça ne passera logiquement pas).
Afficher les 13 commentaires

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.