Si vous faites ce TD sur votre propre ordinateur, il est possible
que vous obteniez une erreur du type
java.lang.OutOfMemoryError: Java heap space. Cela est dû au
fait que les graphes que nous vous faisons manipuler, comportant
beaucoup de sommets (environ 250 000), épuisent toute la mémoire. Si
cela se produit, il faudra augmenter la taille maximale autorisée du
tas. Pour ce faire, dans Visual Studio Code, tapez la
combinaison de touches Ctrl+virgule et indiquez
vm args dans la barre de recherche. L’item
Java>Debug>settings: Vm Args apparaît avec une barre de
texte dans laquelle vous devez ajouter -Xmx1024M à l’option
-ea déjà présente si vous avez fait les TD précédents :
-ea -Xmx1024M.
L’archive src.zip est à
décompresser dans le répertoire TD10 et contient :
Dijkstra et
BiDijkstra à compléter au fur et à mesure du TD,Graph, Node, Edge
(pour la modélisation des graphes) et les classes Fenetre,
ColoredPoint2D, ColoredSegment2D (pour la
visualisation), que vous ne devez pas modifier,Test, Test0,
Test11, … à utiliser pour tester votre code.Le fichier data.zip est également
à décompresser dans le répertoire TD10. Il contient les
données combinatoires et géographiques de deux réseaux routiers.
Ainsi, vous devez vous retrouver avec l’arborescence suivante :
TD10
|--> src
| |--> ColoredPoint2D.java
| \--> ...
\--> data
|--> NY_Metropolitan.png
\--> ...Testez les classes fournies avec le fichier
Test0.java.
Vous devez voir s’afficher la carte de Manhattan et la sortie suivante :
Test 0 : test de la classe Graph
Loading road networks from file mini.gr ... done
Loading road networks from file USA-road-d-NY.gr ... done
Loading geometric coordinates from file USA-road-d-NY.co ... done
Loading background image from file NY_Metropolitan.jpg ... doneNous nous intéressons aujourd’hui au calcul d’un plus court chemin dans un graphe. Lorsque le graphe est un peu gros, comme lors du calcul d’un itinéraire routier, il faut utiliser des algorithmes performants pour obtenir le résultat en un temps acceptable.
Nous allons implémenter le plus simple et le plus classique des algorithmes efficaces pour ce problème, l’algorithme de Dijkstra. Cet algorithme s’applique à des graphes dont les poids des arêtes sont positifs.
GraphOn vous fournit une classe Graph pour représenter des
graphes orientés, de sommets 0, 1, ..., nbVertices-1, et où
les poids des arcs sont des entiers strictement positifs.
Ses principaux champs et méthodes utiles dans la suite sont les suivants :
final int nbVertices donne le nombre de
sommets,Graph(String file) construit un graphe
à partir du fichier file,ArrayList<Integer> successors(int i)
renvoie la liste des successeurs du sommet i,int weight(int i, int j) renvoie le poids de
l’arc (i,j) si ce dernier existe, et
Integer.MAX_VALUE sinon,Graph reverse() renvoie un nouveau graphe où
les orientations des arcs ont été inversées, et les poids
inchangés.La classe Dijkstra fournie contient les champs
suivants :
final Graph g contenant le graphe,final int source contenant la source du plus
court chemin recherché,final int dest contenant la destination du
plus court chemin recherché,Fenetre f nécessaire pour l’affichage
graphique. Vous n’aurez pas à vous soucier de l’initialisation de ce
champ.Le squelette contient un constructeur standard
Dijkstra(Graph g, int source, int dest).
Tout sommet du graphe peut servir de source ou de
dest. En particulier, aucun de ces deux sommets n’est
forcément le sommet 0.
L’algorithme de Dijkstra peut être vu comme une généralisation du parcours en largeur d’un graphe au cas où les arcs sont pondérés mais de poids positifs.
Il fait intervenir
W (working
set) qui contient l’ensemble des sommets déjà rencontrés et
encore à examiner,dist qui indique, pour chaque
sommet i, la distance minimale trouvée entre i
et la source.Initialement :
W contient uniquement la source.0 d’elle-même,
et les autres sommets sont considérés comme étant à une distance
infinie, puisqu’on n’a pas encore trouvé de chemins y conduisant. En
pratique, un entier suffisamment grand fera l’affaire, par exemple
Integer.MAX_VALUE.Tant qu’il reste des sommets à examiner (i.e. W n’est
pas vide) :
W le sommet x, avec la plus
petite valeur dist[x]x est la destination, on renvoie
dist[x],x : pour chaque y
successeur de x, on teste si passer par x pour
rejoindre y fournit un chemin plus court que le meilleur
connu à ce stade, et si c’est le cas on met à jour dist[y]
et on ajoute y à W (on verra en détail plus
loin que faire si y est déjà dans W).À la fin :
W est vide et il aucun chemin n’existe entre la
source et la destination (on renverra alors -1).Nous dirons qu’un sommet a été atteint lorsqu’au moins un chemin a été trouvé entre la source et ce sommet.
Ajoutez à la classe Dijkstra les champs
suivants et modifiez le constructeur pour les initialiser
convenablement :
int[] dist mentionné plus haut,int[] pred où l’entrée pred[i]
indiquera le prédécesseur du sommet i dans le plus court
chemin obtenu entre source et i, ou vaudra
-1 tant que le sommet i n’a pas été
atteint,settled, où
settled[i] sera vrai une fois que l’on aura déterminé la
plus courte distance au sommet i, et faux tant que la
dist[i] n’est qu’une borne supérieure.Nous conviendrons qu’initialement la source est son propre prédécesseur.
Testez avec Test11.java.
Déposez le fichier Dijkstra.java.
WNous voulons pouvoir effectuer efficacement les opérations suivantes
sur l’ensemble W des sommets atteints à traiter :
Nous utilisons pour cela une file de priorité de type
PriorityQueue<Node> qui assure ces opérations en
temps logarithmique en le nombre d’éléments de l’ensemble. La classe
Node utilisée pour représenter les paires (sommet,
distance) est fournie. Les méthodes dont nous aurons besoin sur les
files de priorité sont :
boolean isEmpty() qui renvoie true si et
seulement si la file est vide,void add(Node n) qui ajoute n,Node poll() qui renvoie l’élément dont la distance à la
source est minimale et l’enlève de la file.Il y a une subtilité : les priorités des sommets peuvent être amenées
à changer, (un sommet déjà atteint une première fois peut l’être à
nouveau atteint par un chemin plus court), or la classe
PriorityQueue n’offre pas de moyen efficace de mettre à
jour la priorité d’un élément.
Pour contourner ce problème, lorsque la priorité d’un sommet
i contenu dans l’ensemble W doit être
modifiée, nous insérerons dans W une nouvelle copie de
i avec la nouvelle priorité. Cette nouvelle occurrence de
i sortira forcément de W avant l’ancienne. En
contrepartie, il se pourra qu’un sommet tiré de W soit en
réalité déjà définitivement traité par l’algorithme et il y aura donc
une vérification à faire quand on extrait un sommet.
Ajoutez à la classe Dijkstra un champ
unsettled représentant l’ensemble W. Modifiez
le constructeur de la classe Dijstra pour initialiser
correctement unsettled et y insérer la source.
Testez avec Test12.java.
Déposez le fichier Dijkstra.java
Nous allons maintenant implémenter l’algorithme de Dijkstra en
partant des petites fonctionnalités avant d’assembler le tout. (Cette
manière de procéder nous permettra de réutiliser ensuite la méthode
oneStep() isolément.)
Complétez la méthode
void update(int succ, int current) qui effectue
les mises à jour sur le successeur succ d’un sommet
current pioché dans W. En particulier, si
dist[succ] change, on mettra aussi à jour le prédécesseur
du sommet succ, et on insérera le sommet succ
avec sa nouvelle priorité dans la file unsettled.
Complétez la méthode int nextNode() qui
effectue le choix dans W du sommet current,
avec la plus petite valeur dist[current]. Il s’agit de
retirer de unsettled des sommets dans l’ordre de leur
priorité, jusqu’à rencontrer un sommet non encore traité et le renvoyer.
La méthode doit renvoyer -1 s’il n’a a pas de sommet
atteint non traité.
Complétez la méthode int oneStep() qui
réalise une itération de la boucle principale de l’algorithme de
Dijkstra : extraire de W le prochain sommet
current à traiter, renvoyer -1 s’il ne reste
aucun sommet à traiter, marquer current comme traité,
mettre à jour tous les successeurs de current. La méthode
renverra le sommet current qui vient d’être traité.
Enfin, complétez la méthode
int compute() qui implémente l’algorithme de
Dijkstra à partir des briques précédentes et renvoie la longueur d’un
plus court chemin de source à dest.
Testez en utilisant Test2.java. Vous devez
obtenir :
Test 2 : test de l'algorithme de Dijkstra unidirectionnel utilisant le graphe dans 'mini.gr'...
*** ATTENTION : dans l'affichage, la numérotation des nœeuds commence à 0 ***
*** (et non à 1 comme dans 'mini.gr') ***
Loading road networks from file data/mini.gr... done
Test de la methode update()... [OK]
Test de la methode nextNode... [OK]
Test de la methode oneStep... [OK]
Test de la methode compute... [OK]Maintenant, pour visualiser le résultat, il faut :
slow()
au tout début de la fonction oneStep() (pour ralentir la
visualisation),g.drawUnsettledPoint(f, succ); juste après avoir
ajouté le point succ à l’ensemble
unsettled,g.drawSettledPoint(f, current); juste après avoir
fixé la valeur de settled[current] à
true,Exécutez la classe Test2bis dans le fichier Test2bis.java. Vous
devez voir avancer votre ensemble de points traités (en rouge) et les
points de W (en vert).
À la fin, vous devez obtenir le plus court chemin suivant :
et vous devez voir s’afficher :
plus court chemin entre 190637 et 187333 = 39113Déposez le fichier Dijkstra.java
À partir de maintenant, on suppose qu’il existe toujours au moins un chemin entre la source et la destination.
Nous allons désormais utiliser l’algorithme de Dijkstra pour faire une recherche bidirectionnelle, qui sera généralement plus rapide sur des graphes issus de cartes comme ici.
De manière schématique, dans l’algorithme de Dijkstra, on fait grossir une boule centrée sur la source, et on s’arrête lorsque la destination est contenue dans cette boule. Dans un Dijkstra bidirectionnel, on fait grossir tour à tour deux boules, une centrée sur la source et une centrée sur la destination, jusqu’à ce que ces deux boules se touchent. Si le temps de calcul croît avec le volume des boules, on s’attend à ce que la deuxième méthode soit plus rapide.
Nous allons commencer par une version naïve qui interrompt la recherche dès que les deux boules se touchent. Cela ne donne pas forcément le chemin le plus court, mais nous verrons ensuite comment corriger le problème.
Ouvrez le squelette de la classe BiDijkstra qui contient
les champs suivants :
final Graph g contenant le graphe,final int source contenant la source,final int dest contenant la destination,final Dijkstra forward représentant la recherche de
plus courts chemins à partir de la source,final Dijkstra backward représentant la recherche de
plus courts chemins à partir de la destination,Dijkstra currentDijkstra, otherDijkstra indiquant le
sens de la prochaine itération et celui opposé,private int last contenant le sommet traité par la
dernière itération,private Fenetre f nécessaire pour l’affichage graphique
(vous n’aurez pas à vous soucier de l’initialisation de ce champ).Complétez
BiDijkstra(Graph g, int source, int dest) de votre
classe. On veillera à ce que chaque champ soit correctement initialisé.
En particulier, la recherche arrière doit s’effectuer sur le graphe
inversé et avec les sommets source et destination permutés.void flip() qui inverse la
direction de la recherche, en échangeant currentDijkstra et
otherDijkstra.void oneStep() qui réalise
une itération dans le sens de recherche courant et met à jour le champ
last.boolean isOver() qui
renvoie true si le sommet last a été traité
par la recherche forward et par la recherche
backward. (Dans ce cas, on a trouvé un chemin entre
source et dest, qui passe par le sommet
last.)int getMinPath() qui
renvoie alors le poids du chemin obtenu passant par
last.int compute() qui réalise
l’algorithme de Dijkstra bidirectionnel en utilisant les méthodes
précédentes.Testez avec Test31.java. Vous devez obtenir
:
Test 3.1 : test de l'algorithme de Dijkstra bidirectionnel naif
Loading road networks from file data/mini.gr... done
Test du constructeur BiDijkstra(Graph, int, int)... [OK]
Test de la methode flip()... [OK]
Test de la methode oneStep()... [OK]
Test de la methode isOver()... [OK]
Test de la methode compute()... [OK]
Test de la methode getMinPath()... [OK]
Loading road networks from file data/USA-road-d-NY.gr... done
Loading geometric coordinates from file data/USA-road-d-NY.co ... done
Test de la methode getMinPath()... [OK]Exécutez la classe Test31bis dans le fichier Test31bis.java.
Vous devez voir avancer vos deux paquets de points traités (en rouge) et
leurs frontières (en vert) :
et obtenir le chemin :
Sur ce chemin, le point last est le gros point bleu
central. Dans la console, vous devriez obtenir :
Loading background image from file data/NY_Metropolitan.png ... done
longueur chemin forward entre 190637 et 187333 = 39113
longueur chemin backward entre 190637 et 187333 = 39113
longueur chemin BiDijkstra entre 190637 et 187333 = 39113Déposez le fichier BiDijkstra.java
Exécutez maintenant la classe Test32bis dans le
fichier Test32bis.java, dans
lequel nous avons changé le point source. Quel nouveau phénomène se
produit par rapport à l’exemple précédent ?
Pour comprendre la faiblesse de la méthode naïve et comment la corriger, examinons le schéma suivant.
Dès que le sommet x a été traité par les deux
recherches, nous avons un chemin entre la source et la destination :
l’union des plus courts chemins obtenus entre la source et
x et entre x et la destination. Il se peut que
le plus court chemin ne passe pas par x et donc que le
chemin trouvé ne soit pas le plus court. Lorsque cela se produit, il
existe deux sommets i et j tels que
dist(source, i) + dist(j, dest) +
weight(i, j) < dist(source, x) +
dist(x, dest).
On peut démontrer le fait suivant (preuve plus
bas) : soit x l’unique sommet tel que
forward.settled[x] = backward.settled[x] =
true. Soit a un des chemins les plus courts de
source à dest, et supposons que
length(a) < forward.dist[x] +
backward.dist[x].
Alors le dernier point i sur a (partant de
source) tel que forward.settled[i] =
true est dans backward.unsettled, et l’on
a
length(a) = forward.dist[i] +
backward.dist[i].
Modifiez votre méthode int getMinPath()
afin qu’elle vérifie s’il existe un chemin plus court comme indiqué
ci-dessus et si c’est le cas, mette à jour la variable last
avant de renvoyer la longueur du chemin le plus court.
Testez avec Test32.java et à nouveau avec
Test32bis. Vous devriez cette fois obtenir :
Test 3.2 : test de l'algorithme de Dijkstra bidirectionnel
Loading road networks from file data/USA-road-d-NY.gr... done
Test de la methode getMinPath()... [OK]
longueur chemin forward entre 190637 et 187333 = 35478
longueur chemin backward entre 190637 et 187333 = 35478
longueur chemin bidijkstra entre 190637 et 187333 = 35478Déposez le fichier BiDijkstra.java
Afin de mesurer le gain d’efficacité de la version bidirectionnelle sur la version monodirectionnelle, nous allons compter le nombre d’itérations nécessaires dans chacun des cas.
Modifiez la classe Dijkstra de façon à
compter les appels à oneStep().
Complétez les méthodes
public int getSteps () dans les classes
Dijkstra et BiDijkstra pour
qu’elles renvoient chacune le nombre total d’itérations de l’algorithme
correspondant.
Testez avec Test4.java. Avec la source et la
destination prédéfinies, vous devriez obtenir le résultat suivant. Vous
pouvez comparer le nombre d’étapes requises par les deux algorithmes
pour d’autres paires (source, destination).
Test 4 : comparaisons du nombre d'étapes
Loading road networks from file data/USA-road-d-NY.gr... done
Test de la methode getMinPath()... [OK]
longueur chemin forward entre 190636 et 187333 = 35478 nombre d'étapes = 1252
longueur chemin backward entre 190636 et 187333 = 35478 nombre d'étapes = 1204
longueur chemin BiDijkstra entre 190636 et 187333 = 35478 nombre d'étapes = 621Déposez le fichier BiDijkstra.java
C’est fini pour ce module ! Nous espérons que ces TD ont été instructifs.
Soit j le point qui suit i sur
a. Alors forward.settled[j] =
false et, par conséquent,
forward.dist[j] ≥ forward.dist[x]
(sinon j aurait été traité avant x).
Puisque a passe par j, nous avons
également
forward.dist[j] + backward.dist[j] ≤
length(a) < forward.dist[x] +
backward.dist[x].
Donc
backward.dist[j] < backward.dist[x].
Comme x est traité par backward, j est
aussi traité et donc i est bien dans
backward.unsettled. (Il n’est pas possible que
backward.settled[i] = true, car x
est l’unique sommet traité par les deux recherches.)
Puisque a passe par j, nous avons
forward.dist[i] + backward.dist[i] ≤
length(a).
Si cette inégalité était stricte, cela voudrait dire qu’il y a un
autre chemin de source (ou de dest) à
i plus court que a. Mais alors a
ne serait pas parmi les plus courts chemins satisfaisant les hypothèses
du lemme.