Solution du 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 Le fichier Graphe.java
import java.io.* ;
import java.lang.* ;
import java.util.* ;
public class Graphe {
int nb_sommets ;
Sommet [] sommets ;
boolean [][] aretes ;
// Un constructeur simple
public Graphe(int nbs) {
nb_sommets = nbs ;
sommets = new Sommet[nbs] ;
aretes = new boolean[nbs][nbs] ;
for (int i = 0 ; i < nbs ; i++)
for (int j = 0 ; j < nbs ; j++)
aretes[i][j] = aretes[j][i] = false ;
}
// Construction d'un graphe a partir d'un fichier
public Graphe(String nom_fichier) {
// Ouverture d'un fichier
try {
FileReader fich = new FileReader(nom_fichier) ;
BufferedReader fichier = new BufferedReader(fich) ;
StringTokenizer st = new StringTokenizer(fichier.readLine()) ;
// Lecture des sommets
int nbs = Integer.valueOf(st.nextToken()).intValue() ;
nb_sommets = nbs ;
sommets = new Sommet[nbs] ;
for (int i = 0 ; i < nbs ; i++) {
st = new StringTokenizer(fichier.readLine()) ;
sommets[i] = new Sommet(Integer.valueOf(st.nextToken()).intValue(),
Integer.valueOf(st.nextToken()).intValue(),
Integer.valueOf(st.nextToken()).intValue()) ;
}
// Lecture des aretes
aretes = new boolean[nbs][nbs] ;
st = new StringTokenizer(fichier.readLine()) ;
int nb_aretes = Integer.valueOf(st.nextToken()).intValue() ;
for (int i = 0 ; i < nb_aretes ; i++) {
st = new StringTokenizer(fichier.readLine()) ;
int k = Integer.valueOf(st.nextToken()).intValue(), l = Integer.valueOf(st.nextToken()).intValue() ;
aretes[k][l] = aretes[l][k] = true ;
}
}
// Recuperation des erreurs de lecture
catch(java.io.IOException e) {
System.out.println("Erreur de lecture") ;
System.exit(0) ;
}
}
// Fonction membre d'affichage d'un graphe
void afficher() {
// Calcul de la taille du graphe
int xmax = 0, ymax = 0 ;
for (int i = 0 ; i < nb_sommets ; i++) {
if (xmax < sommets[i].x)
xmax = sommets[i].x ;
if (ymax < sommets[i].y)
ymax = sommets[i].y ;
}
// Ouverture de la fenetre graphique
Rect r = new Rect() ;
r. top = 100 ;
r.left = 100 ;
r.bottom = (short)(r.top + ymax + 20) ;
r.right = (short)(r.left + xmax + 20) ;
MacLib.SetDrawingRect(r) ;
MacLib.ForeColor(MacLib.blackColor) ;
// Dessin des sommets
for (int i = 0 ; i < nb_sommets ; i++)
MacLib.PaintCircle(sommets[i].x, sommets[i].y, 2) ;
// Dessins des aretes
for (int i = 0 ; i < nb_sommets ; i++)
for (int j = 0 ; j < nb_sommets ; j++)
if (aretes[i][j])
MacLib.DrawLine(sommets[i].x, sommets[i].y, sommets[j].x, sommets[j].y) ;
}
}
2 Le fichier Sommet.java
public class Sommet {
int numero, x, y ;
public Sommet(int numero, int x, int y) {
this.numero = numero ;
this.x = x ;
this.y = y ;
}
}
3 Le programme principal.
import java.io.* ;
import java.lang.* ;
import java.util.* ;
public class labyrinthe_dijkstra {
// Algorithme de Dijkstra
/////////////////////////
// La fonction renvoie la longueur du chemin (= le nombre d'aretes a parcourir).
// Le tabelau chemin doit etre initialise.
public static int dijkstra(Graphe graphe, int entree, int sortie, int [] chemin) {
// Initialisation
boolean [] ensemble = new boolean[graphe.nb_sommets] ;
int [] distance = new int[graphe.nb_sommets] ;
int [] pred = new int[graphe.nb_sommets] ;
for (int i = 0 ; i < graphe.nb_sommets ; ++i) {
if (i == entree) {
distance[entree] = 0 ;
ensemble[entree] = true ;
pred[entree] = entree ;
}
else if (graphe.aretes[entree][i]) {
distance[i] = 1 ;
pred[i] = entree ;
ensemble[i] = false ;
}
else {
distance[i] = graphe.nb_sommets + 10 ;
ensemble[i] = false ;
pred[i] = i ;
}
}
// Recherche de tous les chemins
while (true) {
// Recherche du point m
int m = -1, distance_min = graphe.nb_sommets + 11 ;
for (int i = 0 ; i < graphe.nb_sommets ; ++i)
if (!ensemble[i] && distance[i] < distance_min) {
distance_min = distance[i] ;
m = i ;
}
// Test d' arret de la boucle : pas de point m ou m n'est pas relie a CC.
if (m == -1 || distance[m] == graphe.nb_sommets + 10)
break ;
// Mise a jour des tableaux
ensemble[m] = true ;
for (int i = 0 ; i < graphe.nb_sommets ; ++i)
if (graphe.aretes[m][i] && !ensemble[i] && distance[m] + 1 < distance[i]) {
distance[i] = distance[m] + 1 ;
pred[i] = m ;
}
}
// Creation du chemin
return faire_chemin(chemin, pred, sortie) ;
}
// Creation du chemin a partir du tabelau pred.
// La fonction retourne la longueur (en nombre d'aretes) de ce chemin.
public static int faire_chemin(int [] chemin, int [] pred, int i) {
if (pred[i] == i) {
chemin[0] = i ;
return 0 ;
}
int l = 1 + faire_chemin(chemin, pred, pred[i]) ;
chemin[l] = i ;
return l ;
}
// Programme principal
//////////////////////
public static void main(String [] args) {
if (args.length != 3) {
System.out.println("Utilisation : java laryrinthe_dijkstra graphe point_entree point_sortie") ;
System.exit(1) ;
}
// Intialisation du graphique
MacLib.InitQuickDraw() ;
MacLib.ShowDrawing() ;
// Lecture d'un graphe
Graphe graphe = new Graphe(args.length == 0 ? "graphe" : args[0]) ;
graphe.afficher() ;
int entree = Integer.parseInt(args[1]),
sortie = Integer.parseInt(args[2]) ;
int [] chemin = new int[graphe.nb_sommets] ;
int longueur = dijkstra(graphe, entree, sortie, chemin) ;
// Impression du chemin
if (longueur == 0 && sortie == entree)
System.out.println("Le chemin est de longueur nulle : " + entree) ;
else if (longueur == 0)
System.out.println("Il n' y a pas de chemin.") ;
else {
System.out.print("Le chemin est de longueur " + longueur + " : ") ;
for (int i = 0 ; i <= longueur ; i++)
System.out.print(chemin[i] + " ") ;
System.out.println() ;
}
// Affichage du chemin
MacLib.ForeColor(MacLib.redColor) ;
if (longueur != 0) {
for (int i = 0 ; i < longueur ; i++)
MacLib.DrawLine(graphe.sommets[chemin[i]].x, graphe.sommets[chemin[i]].y,
graphe.sommets[chemin[i + 1]].x, graphe.sommets[chemin[i + 1]].y) ;
}
}
}
This document was translated from LATEX by
HEVEA.