Documents publiés » Implémentation de l’algorithme de Dijkstra »

Implémentation de l’algorithme de Dijkstra

Implémentation de l’algorithme de Dijkstra

Résultat renvoyé par l’algorithme

Comme nous l’avons expliqué dans la partie précédente, l’algorithme de Dijkstra renvoie deux tableaux : distances et parcours. D’où la nécessité de créer une structure appropriée en C++ :


struct Res {
   int taille ; // taille du graphe calculé
   Sommet source ; // source des chemins considérés 
   int * distances ; // distances[i] est la distance totale de la source à i
   int * parcours ; // parcours[i] est le sommet précédent i dans le parcours de la source à i	
   Res() ; // constructeur par défaut	
   ~Res() ; // destructeur	
   void Affiche(FILE * f = stdout) ; // Affiche le résultat (sue l’écran ou dans un fichier)
} ;
 

L’algorithme en lui-même

Pas de remarque particulière à faire sur l’implémentation de l’algorithme de Dijkstra en lui-même. Elle ne fait que suivre les étapes précédemment mentionnées en s'appuyant sur les structures de données présentées… Là est tout le secret !

   

Res * Graphe::Djikstra(int source)
{
	Res * resultat = new Res ;
        int * distances = new
        int [taille] ;
	Sommet * parcours = new int [taille] ;
	Sommet * C = new int [taille-1] ;
	MatriceDouble * m =matricialisation() ;
        for (int k=0 ; k<taille ; k++)
	{
		distances[k]=m->rep[source][k] ;
		parcours[k]=source ;
	}
        // Initialisation de C
        for (Sommet i=0, j=0 ; i<taille ; i++)
	{
                if (i!=source)
		{
			C[j]=i ;
			j++ ;
		}
	}
	Tas * T = new Tas(C, taille-1, (fptr) inf_str, distances, vrai) ;
	T->Tri() ;
        for (i=0 ; i<taille -2; i++)
	{
		Sommet mini = T->ExtrMinimum() ;
                for (Rayons * l = m->adresse[mini]->sommet.liste ; l!=NULL ; l=l->suivant)
		{
			Sommet s = l->fleche.extrem ;
                        if (inf_str(somme(m->rep[mini][s] , distances[mini]),distances[s]))
			{
				distances[s]=somme(m->rep[mini][s] , distances[mini]) ;
				parcours[s] = mini ;
				T->Percolation (T->Inverse(s)) ;
			}
		}
	}
        delete m ;
        delete T ;
        delete [] C ;
	resultat->distances = distances ;
	resultat->parcours = parcours ;
	resultat->taille = taille ;
	resultat->source = source ;
        return resultat ;
}

Petite interface

Qu'attendons-nous pour tester l’algorithme sur quelques graphes de notre cru ? Une petite interface conviviale ? Qu'à cela ne tienne, définissons un objet menu :

   

class Menu
{
        char * nom ; // Titre du menu
        int taille ; // Nombre d’options proposé
        char * * composants ; // Tableau contenant le nom des options proposées
        char * acces ; // tableau contenant les lettres qui permettent de choisir une option donnée
        static int est_dans(char, char *) ; // teste si char est dans char * et renvoie sa position dans char * s'il existe
   public :
	Menu(char *, int, char * *, char *) ; // Constructeur paramétré (nom, taille, tableau de composantes, table d’accès)
	~Menu() ; // destructeur
        void Affiche() ; // Affichage du menu
        int Reponse () ; // Attente de la réponse
} ;

Dans notre cas, le menu proposé est le suivant :


   *** Menu principal ***
   
   [G] : creation interactive d’un Graphe
   [A] : Afficher un graphe
   [C] : Charger un graphe en format texte
   [S] : Sauver un graphe en format texte
   [T] : Trouver les plus courts chemins
   [E] : Enregistrer le resultat
   [Q] : Quitter
   
   Votre choix ?

La création interactive d’un graphe se comprend sans problème ; il faut juste décider au départ si on souhaite obtenir un graphe symétrique ou non (i.e. "des routes avec ou sans sens interdit"). Trouver les plus courts chemins lance bien entendu l’algorithme de Dijkstra une fois le sommet source précisé. Pour des raisons de commodité de programmation lors de l’appel récursif nécessaire pour trouver un chemin le plus court à proprement parler, les chemins les plus courts sont affichés dans l’ordre inverse, c'est-à-dire qu'il faut simplement les lire de droite à gauche…Il reste à dire un mot sur les formats de fichiers utilisés pour représenter les graphes… Se reporter à la partie suivante pour quelques exemples concrets :


   Taille : n
   Sommet : n
      Extremite : i
      Poids : pi
      …
      Extremite : j
      Poids : pj
      …   
   Sommet : n-1
      …
      …
   Sommet : 0
      …
      Extremite : k
      Poids : pk

L’ordre des sommets, tout comme l’ordre des arêtes, importe peu pourvu que les sommets apparaissent tous une et une seule fois (le programme de lecture commence par lire la taille du graphe et recherche alors les n sommets correspondants).

Deux petits exemples

Reprenons l’exemple du graphe S={d,a,o,u,s,t} , en renumérotant les sommets de 0 à 5 et en supprimant l’arête (d,d) (le plus court chemin de d à lui-même est nécessairement 0). Certes, ce graphe n’est pas connexe, mais tant qu'on ne s'occupe pas des chemins qui n’existent pas, l’algorithme fonctionne à merveille…

Schema du graphe {d,a,o,u,s,t}


Taille : 6
Sommet : 5
Extremite : 4
Poids : 5
Sommet : 4
Extremite : 5
Poids : 3
Extremite : 2
Poids : 4
Sommet : 3
Extremite : 4
Poids : 1
Sommet : 2
Extremite : 3
Poids : 3
Sommet : 1
Extremite : 3
Poids : 7
Extremite : 2
Poids : 1
Sommet : 0
Extremite : 1
Poids : 2

Lançons Dijkstra sur le sommet 0 :


   Source : 0
   Parcours a l’envers de 0 a 1 :
   1 0
   Distance : 2
   Parcours a l’envers de 0 a 2 :
   2 1 0
   Distance : 3
   Parcours a l’envers de 0 a 3 :
   3 2 1 0
   Distance : 6
   Parcours a l’envers de 0 a 4 :
   4 3 2 1 0
   Distance : 7
   Parcours a l’envers de 0 a 5 :
   5 4 3 2 1 0
   Distance : 10

Pour les amateurs, un graphe un peu plus gros, et connexe cette fois :

Un deuxieme exemple de graphe


Taille : 8
Sommet : 7
Extremite : 4
Poids : 2
Extremite : 2
Poids : 3
Extremite : 0
Poids : 3
Sommet : 6
Extremite : 5
Poids : 1
Extremite : 3   
Poids : 4   
Extremite : 0   
Poids : 1   
Sommet : 5   
Extremite : 6
Poids : 2   
Sommet : 4   
Extremite : 7
Poids : 5   
Extremite : 5   
Poids : 1   
Extremite : 3   
Poids : 2   
Sommet : 3   
Extremite : 6   
Poids : 7   
Extremite : 7   
Poids : 3   
Sommet : 2   
Extremite : 4   
Poids : 4  
Sommet : 1   
Extremite : 7   
Poids : 1   
Sommet : 0   
Extremite : 7   
Poids : 3   
Extremite : 4   
Poids : 3   
Extremite : 2
Poids : 8  
Extremite : 1   
Poids : 1

C'est parti pour un petit Dijkstra appliqué au sommet 6…


   Source : 6
   Parcours a l’envers de 6 a 0 :
   0 6
   Distance : 1
   Parcours a l’envers de 6 a 1 :
   1 0 6
   Distance : 2
   Parcours a l’envers de 6 a 2 :
   2 7 1 0 6
   Distance : 6
   Parcours a l’envers de 6 a 3 :
   3 6
   Distance : 4
   Parcours a l’envers de 6 a 4 :
   4 0 6
   Distance : 4
   Parcours a l’envers de 6 a 5 :
   5 6
   Distance : 1
   Parcours a l’envers de 6 a 7 :
   7 1 0 6
   Distance : 3