Structure de données utilisée :

Nous avons en fait implémenté trois classes :

• la classe graph qui représente le graphe à traiter. Cette classe a pour attributs le nombre de sommets du graphe et un tableau de sommets.
  
• la classe sommet, elle, représente tout simplement un sommet, c'est-à-dire son code (numéro dans le graphe) et une liste chaînée de sommets contenant des informations sur les extrémités finales des arcs dont il est l'extrémité initiale. Le fait de choisir la liste chaînée pour représenter cette liste nous a paru évident, étant donné que l'on ne connaît pas le nombre d'éléments de celle-ci à l'avance.
  
• la classe list_sommet sert à stocker la liste cité précédemment. Elle comprend un pointeur sur le sommet étant l'extrémité finale de l'arc, le poids de cet arc et bien sûr sur l'élément suivant de la liste.

Déclaration de ces classes :

• /////////////////// classe sommet /////////////////////////////////
  
  class sommet
  /* chaque sommet contient une liste de successeur et son numéro dans le graph.*/
  {
  unsigned int code; //numéro du sommet
  list_sommet * succ; //liste des successeurs
  
  public:
  //constructeurs et destructeur
  sommet(){succ=NULL;}
  sommet(unsigned int c):code(c) {succ=NULL;}
  ~sommet(){ supprime_liste();}
  //suppression de la liste des successeurs de la mémoire
  void supprime_liste();
  //ajout d'un successeur dans la liste du sommet
  void ajout_liste(sommet * s,const unsigned int p);
  //affichage du numéro du sommet ainsi que de ses successeurs
  void affiche() const;
  //renvoie si le sommet a pour successeur le sommet dont le numéro est passé en paramètre
  int a_pour_succ(const unsigned int c) const;
  //partage des données avec la classe graph
  friend class graph;
  };

• /////////////////// classe list_sommet ////////////////////////////
  
  class list_sommet
  /*chaque élément de la liste de sommet contient le poids de l'arc entre le sommet qui génère la liste et le sommet dont l'adresse est stockée dans l'attribut "contenu"*/
  {
  int poids; //poids de l'arc
  sommet * contenu; //pointeur sur le sommet correspondant
  list_sommet * suivant; //suivant dans la liste
  public:
  //partage des données avec les classes graph et sommet
  friend class sommet;
  friend class graph;
  };
  
  
• /////////////////// classe graph //////////////////////////////////
  
  class graph
  {
  unsigned int nbs; //nombre de sommets du graph
  sommet * tabsommet; //tableau de sommets du graph
  public:
  //constructeurs et destructeur
  graph():nbs(0){}
  graph(const unsigned int n) : nbs(n) { tabsommet = new sommet [n];
  for (unsigned int i=0;i<n;i++) tabsommet[i].code=i;}
  ~graph() { if (nbs>0) delete [] tabsommet; }
  //affichage du graphe : liste des sommets et de leurs successeurs
  void affiche() const;
  //formation d'un arc de poids p, du sommet d au sommet a
  void ajout_succ(const unsigned int d,const unsignedint a,const unsignedint p);
  //on test si S a tous ses sommets marqués
  int test(const unsigned int * s) const;
  //algorithme de Dijkstra
  graph * dijkstra(unsigned long int & temps) const;
  //chargement d'un garphe à partir d'un fichier
  void charger();
  //enregistrement d'un graphe dans un fichier
  void enregistrer() const;
  //propose à l'utilisateur d'afficher en d'enregistrer un graphe
  void sortie_graphe();
  //génération aléatoire de graphe ayant n sommets
  void hasard(const unsigned int n,const unsignedint proba);
  //verifie si un graphe est connexe en utilisant un parcours en largeur, et dans le cas échéant le rend connexe
  //renvoie un si une correction a été apportée
  int connexe();
  };
  

Voici un exemple illustrant cette structure de données :

Algorithme :

Soit un graphe de n sommets. On considère que ce graphe ne contient pas de circuit négatif (c'est-à-dire, qu'il ne contient pas d'arc ayant un poids négatif). On appelle Pi(x) la plus courte distance entre le sommet source s (dans notre cas ce sera le sommet numéro 0) et le sommet x. On appelle distance la somme des arcs parcourus pour aller d'un sommet à un autre.

Variables utilisées :

• S : un tableau de n entiers, dont l'élément i contiendra la valeur 1 si le sommet est marqué, 0 sinon.
• Pi : un autre tableau de n entiers, dont l'élément i contiendra tout simplement Pi(i), cette valeur n'étant pas exact initialement, et s'affinant au fur et à mesure de l'algorithme.
• xpivot : un entier contenant le code (numéro) du sommet traité.
• graph : étant le graphe résultant de l'algorithme
• courant : pointeur dans la liste des successeurs d'un sommet.

Initialisation :

• Pour tout i, i=0 jusqu'a n faire S[i]= 0
• Pour tout i , i=0 jusqu'a n faire Pi[i]=infini (on initialise une constante à une très grande valeur que l'on estime supérieure à tous les poids des arcs du graphe )
• Pi(0)= 0 ( le poids du sommet de départ est nul )
• S(0)= 1 ( marquage du premier sommet )
• Création de graph enmémoire ( avec tous les sommets, mais aucun arc pour l'instant )
• xpivot=0 (le premier pivot est le premier sommet du graphe )

Parcours du graphe et calcul du plus court chemin :

Tant que il existe un i tel que S(i)=0 ( tant qu'il existe un sommet non marqué dans le graphe de départ )
et que Pi(xpivot)<infini
Faire
courant=tabsommet[xpivot].succ ( on initialise le pointeur courant sur le premier successeur de xpivot )
déclaration d'un entier x
Tant que courant != NULL faire
x=code du sommet successeur
Si Pi(x) > Pi(xpivot) + *courant.poids alors Pi(x)=Pi(xpivot) + *courant.poids
Fin Tantque
déclaration d'un entier min (pour le stockage du Pi minimum )
Pour tout sommet i Si S(i)=0 ( s'il le sommet n'est pas marqué )
alors Si Pi(i)<min alors min=Pi(i) et xpivot=i
Finsi
Fin Pour
S(xpivot)=1 ( marquage du sommet pivot )
Pour tout i : sommet marqué faire
courant=tabsommet[i].succ ( on initialise le pointeur courant sur le premier successeur de i )
Tant que courant != NULL et code du courant!= xpivot faire courant=courant.suivant
Si (courant!=NULL) alors
Si (Pi[xpivot]=(Pi[i] + courant->poids)) alors ajout de l'arc (i,xpivot) dans graph
Finsi
Fin Pour
Fin Tantque

Réalisation du programme :

• structure.h : fichier en-tête qui contient toute la structure de données ainsi que ses méthodes
• structure.cpp : l'implémentation de ces méthodes
• graph.cpp : programme principal

Pour télécharger les sources et le makefile , choisissez le format de l'archive :

• format zip
• format rar

!!! Important !!! Pour compiler les sources, si vous êtes sous visual C++, vous devez avoir au début du fichier graph.cpp ceci :

#define visualcpp
//#define autres_compilos

Sinon, si vous êtes avec Borland C++ ou g++, vou devez inversez les commentaires, pour avoir :

//#define visualcpp
#define autres_compilos

Pour plus d'explication, jetez un coup d'oeuil dans les sources, c'est expliqué!

Pour faire plus simple, vous pouvez télécharger l'exécutable pour Windows : executable

Pour en savoir plus sur le contenu des classes et les procédures et fonctions, consultez le listing commenté.

Vérification de la connexité du graphe :

(ou comment ne pas faire tourner un programme en rond)

En effet, si le graphe n'est pas connexe, notre algorithme "tourne en boucle". Pour remédier à cela, on a créé la fonction grap::connexe() qui :

• teste si un graphe est connexe : pour cela, nous allons utilisé l'algorithme de parcours en largeur c'est-à dire qu'on commence par marquer le premier sommet, puis on marque ses voisins, puis les voisins de ces voisins ... A la fin de ce marquage, s'il existe des sommets non marqués, c'est que le graphe n'est pas connexe, car ces sommets appartiennent à une (ou plusieurs) composante(s) connexe(s) qui ne contiennent pas le sommet source.
• le rend connexe, le cas échéant : Pour cela, on connecte ces sommets isolés au reste du graphe en ajoutant des arcs.

A propos de la génération aléatoire :

Nous avons dévellopez une fonction pour générer aléatoirement des graphes.

Cette fonction prend deux paramètres : le nombre de sommets que le graphe doit contenir et le pourcentage de chance que deux sommets soit relié par un arc. Pour cela on parcours simplement le graphe, et pour chaque sommet i, on parcours à nouveau le graphe, excépté le sommet i, et pour chaque sommet j, on tire un nombre aléatoire compris entre 0 et 100, et si ce nombre est inférieur au coefficient passé en paramètre, alors on crée un arc entre le sommet i et le sommet j avec un poids tiré aléatoirement. Puis on vérifie que le graphe trouvé est bien connexe, le cas échéant, on le rend connexe avec la fonction cité plus haut.

Résultats obtenus :

Tous ces tests ont été effectués avec un K6-2 300 MHz et 128Mo de RAM.

Après avoir calculer les moyennes de temps, nous nous sommes interressé à comment pouvoir les comparer avec la complexité théorique qui est, rappelons le en o(n²). Nous avons donc, tout d'abord calculé la valeur de n² pour chaque quantité de sommet. Puis nous avons décidé qu'il fallait que ces courbes aient en commun deux points le premier (l'origine 0) et le dernier. Donc pour 1000 sommets, nous retrouvons les même valeurs pour le temps d'exécution et la courbe théorique. Pour les autres quantité de sommets il suffit de diviser la valeur de n² corrsepondante par 1000000 puis de la multiplier par 14382. Ainsi, par exemple, pour 600 sommets on trouve (360000/1000000)*14382=5177.52.

Comparaison complexité pratique / théorique :

Interprétation des résultats :

Nous allons baser notre analyse sur la courbe ci dessus. Cette courbe représente la complexité théorique ainsi que la complexité pratique. A première vue, les courbes ont le même profil. On remarque nettement que la complexité pratique est inférieure à la complexité théorique, ce qui se justifie par le fait que la complexité théorique se base sur le pire des cas, et ce cas là est rarement atteint, voire impossible avec une génération aléatoire.

dernière mise à jour : mardi 15 mai 2001
Licence d'informatique - Université Blaise Pascal - Clermont-Ferrand