TD d'informatique No. 9 : Graphes et labyrinthes, suite

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 22 janvier 2001

1 Préliminaires

Ce TD prend la suite de celui de la semaine dernière. On commencera par modifier la classe Graphe pour rendre les graphes non orientés. Il est ensuite demandé à ceux qui ne l'auraient pas fait, de programmer la méthode de recherche d'un chemin dans le graphe par fil d'Ariane (recherche en profondeur d'abord).

2 Dijkstra

Dans un deuxième temps, on propose d'utiliser un autre algorithme, dit algorithme de Dijkstra.

Le principe de cet algorithme est le suivant. On construit progressivement un ensemble CC des sommets x du graphe pour lesquels on connaît un plus court chemin du point de départ s à x. Le complémentaire de CC est noté M. Au départ, CC ne contient que s.

À chaque étape, on ajoute a CC le sommet m de M qui vérifie la propriété suivante : m est le sommet de M qui a le plus court chemin jusqu'à s en ne passant que par des sommets de CC.

Pour coder cet algorithme, on utilise les données suivantes :

un tableau ensemble de booléens dont la taille est le nombre de sommets, code par true l'appartenance d'un sommet a CC, par false son appartenance à M ;
un tableau distance donne pour tout sommet de M la distance de son plus court chemin à s en ne passant que par des sommets de CC ;
un tableau pred donne pour chaque sommet de M son prédécesseur sur ce plus court chemin de s à m en ne passant que par CC.

On utilise par ailleurs une fonction cout telle que cout(x, x) = 0 pour tout sommet x, cout(x, y) = 1 s'il existe une arête entre x et y, et cout(x, y) = ¥ si une telle arête n'existe pas.

L'algorithme procède ainsi :

initialisation des tableaux ensemble, distance et pred, seul s appartient à CC ;
tant que M n'est pas vide, chercher le prochain point m à considérer ; si distance(m) = ¥, alors la boucle est finie ;
mettre m dans CC ;
mettre à jour les valeurs de distance et pred des sommets de M adjacents à m si passer par m permet de trouver une chemin plus court jusqu'à s ;
fin de la boucle sur m ;
il ne reste plus qu'à lire les données accumulées pour trouver le chemin cherché ;

3 Programmation objet

On pourra essayer de programmer d'une manière plus orientée objet. Pour cela, on peut associer à chaque classe des fonctions membres. Ces fonctions sont déclarées dans la classe sans le mot clé static. Elles sont appelées par le biais d'un objet, et prennent cet objet comme argument implicite. Les champ de cet objet peuvent être désignés directement, ou par l'intermédiaire du mot clé this.

Voici un exemple :

public class fiche {
   String nom ;
   String prenom ;
   int no_cie ;

// Un constructeur
public fiche(String n, String p, int n) {
   nom = n ;
   prenom = p ;
   no_cie = n ;
}

// Une fonction membre
public void afficher() {
   System.out.println(nom + ' ' + prenom + ' ' + no_cie + "e Cie") ;
}

// Meme chose ecrit differemment
public void afficher2() {
   System.out.println(this.nom + ' ' + this.prenom + ' ' + this.no_cie + "e Cie") ;
}
}

On pourra en particulier créer une classe Chemin pour améliorer la structuration du programme.