TD 10 - Plus courts chemins

Votre opinion sur le cours de ce lundi : Votre opinion sur le TD de la semaine dernière :

 Login :  Mot de passe :

À télécharger

Tout d'abord, les fichiers à télécharger et décompresser:

Testez les classes fournies avec le fichier Test0.java.

Vous devez alors voir s'afficher :

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 ... done

et la carte :

Remarque : Si vous faites ce TD ailleurs qu'en salle machine, il est possible que vous obteniez une erreur du type Exception in thread "main" java.lang.OutOfMemoryError: Java heap space, cela est du au fait que les graphes que nous vous faisons manipuler, comportant beaucoup de sommets (environ 250 000), épuisent toute la mémoire. Il faut donc augmenter la taille maximale autorisée du tas. Pour cela, sélectionner Run configurations ... dans le menu Run d'Eclipse et ajouter la ligne -Xmx1024M dans VM arguments.

Préambule

Le sujet d'aujourd'hui

Nous allons aujourd'hui nous intéresser au problème du calcul d'un plus court chemin dans un graphe. C'est un problème qui se pose par exemple dans les logiciels de GPS qui doivent calculer des itinéraires routiers. Lorsque les graphes sont gros, il faut utiliser des algorithmes performants pour calculer des plus courts chemins en un temps acceptable par l'utilisateur : c'est bien le cas des réseaux routiers, qui correspondent à des graphes avec plusieurs centaines de milliers (voir millions) de sommets.

Itinéraire calculé par Google Maps, entre le Metropolitan Museum of Art et le Intrepid Sea, Air & Space Museum (New York City).

Nous allons implémenter l'algorithme de Dijsktra. Cet algorithme s'applique à des graphes connexes dont les poids des arêtes sont positifs ou nuls. Nous implémenterons ensuite un algorithme de recherche bidirectionnelle basé sur Dijkstra. Les animations ci-dessous illustrent les deux algorithmes que vous allez coder aujourd'hui.

La Classe Graph

Nous allons travailler sur des graphes orientés où les poids des arcs sont des entiers strictement positifs. Par convention, les sommets seront les entiers 0, 1, ..., n-1. On vous fournit la classe Graph dont les champs et méthodes publiques sont les suivants :

Il n'est pas utile de lire le code de la classe Graph, la description ci-dessus est suffisante pour l'utiliser dans ce TD.

Rappel de l'algorithm de Dijkstra

Notre problème consiste à calculer la longueur d'un plus court chemin entre un sommet source et un sommet destination dans un graphe orienté. Pour ce faire, nous allons coder l'algorithme de Dijkstra. La classe Dijkstra fournie contient les champs suivants :

Le squelette contient un constructeur standard Dijkstra(Graph g, int source, int dest).

Attention: Tout sommet du graphe peut servir de source ou de dest. En particulier, aucun de ces deux sommets n'est obligé à être le sommet 0.

Rappelons comment fonctionne l'algorithme de Dijkstra. Cet algorithme fait intervenir la manipulation des informations suivantes

L'algorithme procède comme suit.

Pour résumer

Cet algorithme fait intervenir

dans la suite, nous allons progressivement introduire ces trois éléments.

1. Au boulot !

1.1. Les bases

Tout d'abord, ajoutez un champ int[] dist à la classe Dijkstra et mettez à jour le constructeur de la classe Dijkstra afin de l'initialiser correctement.

Nous allons ajouter les informations suivantes, que nous maintiendrons durant le déroulement de l'algorithme :

Par ailleurs, nous dirons qu'un sommet a été atteint lorsqu'au moins un chemin a été trouvé entre la source et ce sommet. Ce qui revient à dire qu'un sommet a été atteint lorsque son prédécesseur est différent de -1. Pour la source, nous conviendrons qu'initialement elle est son propre prédécesseur et qu'elle n'est pas encore traitée.

Ajoutez ces champs à la classe Dijkstra, et modifiez le constructeur de sorte que ces champs soient correctement initialisés.

Afin de vérifier votre classe Dijkstra, exécutez le fichier Test11.java. Vous devez obtenir :

Test 1.1 : Initialisation de la classe Dijkstra
Loading road networks from file mini.gr ... done
Test de source... [OK]
Test de dest... [OK]
Test de dist, pred et settled... [OK]

Déposez le fichier Dijkstra.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

1.2. L'ensemble W

Dans la description de l'algorithme de Dijkstra apparaît un ensemble noté W qui correspond aux sommets atteints mais pas encore traités. Sur cet ensemble, nous voulons pouvoir faire les opérations suivantes:

Pour être efficace, nous savons que nous pouvons assurer ces deux opérations en temps logarithmique en le nombre de sommets contenus dans cet ensemble, à condition d'utiliser une structure appropriée. En l'occurrence, nous allons utiliser ici une file de priorité, qui permet l'ajout d'un élément et le retrait du minimum en temps logarithmique. La priorité d'un élément sera définie par sa distance à la source.

Il y a toutefois une subtilité. Les priorités des sommets peuvent être amenées à changer, par exemple si un sommet déjà atteint est de nouveau atteint via un chemin plus court. Dans un tel cas, il faut pouvoir modifier la priorité de cet élément dans la file de priorité, ce qui est assez complexe. Nous allons habilement contourner ce problème en faisant la chose suivante : lorsque la priorité d'un sommet i contenu dans l'ensemble W doit être modifiée, nous insérerons dans W une nouvelle occurrence de i avec la nouvelle priorité. Nous savons que cette nouvelle occurrence de i sortira de W avant l'ancienne, puisque les éléments sortent par ordre croissant. En contrepartie, il se pourra qu'un sommet sorti de W soit déjà définitivement traité par l'algorithme et il faudra donc le vérifier.

Nous allons donc utiliser une file de priorité qui contiendra des éléments de type Node, composé d'un identifiant id (le numéro du sommet) et d'une valeur val (sa priorité, c'est-à-dire sa distance à la source). Pour créer un sommet correspondant au sommet id, nous utiliserons le constructeur Node(int id, int val).

Ajoutez un champ PriorityQueue<Node> unsettled à la classe Dijkstra. Ce dernier représentera l'ensemble W dans la description de l'algorithme. Modifiez le constructeur de la classe pour initialiser correctement unsettled et y insérer la source.

Les méthodes dont nous aurons besoin sur les files de priorités seront classiquement :

Testez avec le fichier Test12.java. Vous devez obtenir :

Test 1.2 : Initialisation de la classe Dijkstra
Loading road networks from file mini.gr ... done
Test de unsettled (ensemble W)...[OK]

Déposez le fichier Dijkstra.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2. Dijkstra unidirectionnel

Nous avons désormais tout ce qu'il faut pour coder une version efficace de l'algorithme de Dijkstra.

Complétez la méthode void update(int succ, int current), qui effectuera les mises à jour sur les successeurs du sommet current, pioché dans W dans le corps de la boucle. En particulier, dans le cas où une mise à jour est effectuée sur dist[succ], on mettra à 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 effectuera le choix dans W du sommet current, avec la plus petite valeur dist[current]. Il s'agirait de retirer de unsettled des sommets dans l'ordre de leur priorité, jusqu'à rencontrer un sommet non encore traité et le renvoyer. Renvoyer -1 si la file de priorité est vide ou si tous les sommets restant dans la file ont déjà été traités.

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, renvoyer le sommet current qui vient d'être traité.

Enfin, complétez la méthode int compute() qui calcule et renvoie la longueur d'un plus court chemin. Elle fonctionnera de la manière suivante : tant qu'on n'a pas traité la destination et qu'il reste au moins un sommet à traiter, on réalise une itération. Ensuite, on renvoie -1 ou la valeur du plus court chemin suivant que la destination a été atteinte ou non.

Testez vos méthodes avec le fichier Test21.java. Vous devez obtenir :

Test 2.1 : test de l'algorithme de Dijkstra basique ...
Loading road networks from file mini.gr ... done
Loading road networks from file USA-road-d-NY.gr ... done
[OK]

Et maintenant pour visualiser le résultat, il faut :

À la fin, vous devez obtenir le plus court chemin suivant :

et vous devez voir s'afficher :

Test 2.2 : test de l'algorithme de Dijkstra basique sur un gros graphe
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 ... done
plus court chemin entre 190637 et 187333 = 39113

Déposez le fichier Dijkstra.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3. Dijkstra bidirectionnel

À partir de maintenant, on suppose qu'il existe toujours au moins un chemin entre la source et la destination.

L'algorithme

Nous allons désormais utiliser l'algorithme de Dijkstra pour faire une recherche bidirectionnelle, qui sera plus rapide sur des graphes standards.

De manière schématique, dans un Dijkstra classique, on fait grossir une boule centrée sur la source, et on s'arrête lorsque la destination est incluse 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. La surface des boules représentant schématiquement le temps de calcul, il est facile de s'imaginer que le Dijkstra bidirectionnel doit être plus rapide, dans le cas où les graphes ne sont pas trop bizarres.

Illustration de différence entre Dijkstra uni- et bi-directionnel

3.1. Première implémentation naïve

Ouvrez le squelette de la classe BiDijkstra qui contient les champs suivants :

Complétez

Testez votre classe avec le fichier Test31.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 :

Test 3.1 : test de l'algorithme de Dijkstra bidirectionnel naif
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.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 = 39113

Déposez le fichier BiDijkstra.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3.2. Le calcul final du plus court chemin

Testez maintenant avec le fichier Test32.java, dans lequel nous avons changé le point source. Vous devez voir s'afficher :

et obtenir le chemin :

Dans la console, vous devriez obtenir :

Test 3.2 : test de l'algorithme de Dijkstra bidirectionnel
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.png ...  done
longueur chemin forward    entre 190636 et 187333 = 35478
longueur chemin backward   entre 190636 et 187333 = 35478
longueur chemin bidijkstra entre 190636 et 187333 = 35489

Quelle anomalie constatez-vous ?

Nous avons un problème. Examinons le schéma suivant :

Illustration du raffinement du BiDijkstra

Dès lors que le sommet x a été traité par les deux recherches, nous avons un candidat potentiel au plus court 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. Pourtant, il se peut que ce chemin ne soit pas le plus court. En effet, un chemin plus court peut exister comme illustré dans le dessin ci-dessus, à condition que

dist(source, i) + dist(j, dest) + weight(i, j) < dist(source, x) + dist(x, dest)

On peut alors démontrer (preuve plus bas) le fait suivant :

« Soit x l'unique sommet, tel que

forward.settled[x] = backward.settled[x] = true.

Soit α un chemin le plus court de source à dest, tel que

length(α) < forward.dist[x] + backward.dist[x].

Alors le dernier point i sur α (partant de source), tel que forward.settled[i] = true, est dans backward.unsettled et

length(α) = 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 à nouveau avec le fichier Test32.java. Vous devez maintenant voir s'afficher :

et obtenir le chemin :

Dans la console, vous devriez obtenir :

Test 3.2 : test de l'algorithme de Dijkstra bidirectionnel
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.png ...  done
longueur chemin forward    entre 190636 et 187333 = 35478
longueur chemin backward   entre 190636 et 187333 = 35478
longueur chemin bidijkstra entre 190636 et 187333 = 35478

Déposez le fichier BiDijkstra.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4. Comptons

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.

Dans la classe Dijkstra, ajoutez un champ private int steps. Initialisez-le dans le constructeur, et incrémentez-le dans la méthode oneStep().

Complétez les méthodes public int getSteps () dans les deux classes Dijkstra et BiDijkstra pour qu'elles renvoient les nombres d'itérations correspondants

Testez ce compteur avec le fichier Test4.java. Comparer le nombre d'étapes nécessaires pour chacune des recherches. Vous devriez obtenir :

Test 4 : comparaisons du nombre d'étapes
Loading road networks from file USA-road-d-NY.gr ... done
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 = 621

Bien entendu, vous pouvez changer la source et la destination et relancer.

Déposez les fichiers Dijkstra.java et BiDijkstra.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Solutions

Voici une proposition de solutions :

Preuve du fait énoncé plus haut pour le calcul final du plus court chemin

On voudrait démontrer le fait suivant :

« Soit x l'unique sommet, tel que

forward.settled[x] = backward.settled[x] = true.

Soit α un chemin le plus court de source à dest, tel que

length(α) < forward.dist[x] + backward.dist[x].

Alors le dernier point i sur α (partant de source), tel que forward.settled[i] = true, est dans backward.unsettled et

length(α) = forward.dist[i] + backward.dist[i]. »

Preuve : Soit j le point qui suit i sur α. Alors forward.settled[j] == false et, par conséquence,

forward.dist[j] ≥ forward.dist[x]

(sinon j aurait été traité avant x). Puisque α passe par j, nous avons également

forward.dist[j] + backward.dist[j] ≤ length(α) < 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 tel sommet).

Puisque α passe par j, nous avons

forward.dist[i] + backward.dist[i] ≤ length(α).

Si cette inégalité était stricte, cela aurait voulu dire qu'il y a un autre chemin de source (ou de dest) à i plus court que celui, qui suit α. Mais alors α ne serait pas parmi les plus courts chemins satisfaisant les hypothèses du lemme. On conclut, donc, que

length(α) = forward.dist[i] + backward.dist[i]. ∎