Objectifs

  • Coder les structures nécessaires à l'algorithme de Dijkstra.
  • Puis l'algorithme de Dijkstra proprement dit.

Prérequis

Consignes

Tous les tests JUnit de la classe Path doivent passer !
Carte

Dans peu de temps, vous développerez avec joie un algorithme de Dijkstra pour calculer le plus court chemin (en distance ou en temps de trajet) entre un sommet origine et un sommet destination. Mais avant cela, il vous faut une structure nécessaire à l'algorithme : le tas.

Le Tas

  • Retrouvez le principe d'un tas (vu en 2MIC). Quelles sont les méthodes élémentaires sur un tas ?
    À défaut, regardez cette vidéo
    Questions de compréhension / réflexion :
    • Lors de l'agorithme de Dijkstra, l'étape de sélection d'un sommet de cout minimal doit se baser sur un tas. Savez-vous pourquoi ?
    • Que contient le tas juste après l'étape d'initialisation de l'algorithme ?
    • Quelle est la complexité théorique de l'algorithme de Dijkstra sans tas et avec tas ?
  • Vérifiez que vous avez une version à jour des classes : git pull
  • Dans main.org.insa.algo.utils vous trouvez la classe BinaryHeap qui n'est pas tout à fait complète. Il manque la méthode remove qui permet de retirer un élément quelconque du tas. Lancez les tests JUnit concernant le tas : certains échouent.
  • Écrivez la méthode manquante. Dans un premier temps, vous pouvez utiliser indexOf, mais en vous demandant si c'est bien raisonnable.
    • ForbiddenN'utilisez pas la méthode remove de ArrayList, dont la complexité est incertaine.
    • Et puis un tas est censé se baser sur un tableau standard... en principe, on ne peut pas retirer une case d'un tableau.
    • BinaryHeap utilise une ArrayList car en Java les tableaux standard (array[]) sont difficilement utilisables en présence de généricité (ce qui est consternant).
    • Si vous envisagez de remplacer indexOf par un FOR ou un WHILE qui parcourt le tableau, cela ne sert à rien : indexOf est déjà implémenté comme ça.
  • Pour passer à la suite, il faut que les tests JUnit du tas soient satisfaits.
    Et vous n'oubliez pas git pull, git add .., git commit -m .., git push
Questions de compréhension / réflexion :
  • Concernant les tests JUnit du tas : le programmeur expérimenté qui a écrit les tests JUnit du tas avait-il besoin de la classe BinaryHeap pour écrire les tests ?
    Cette question soulève un principe de conception important, cela vaut la peine d'y réfléchir 5 minutes... puis de chercher Test Driven Development sur le internet.
  • Si vous ajoutez des méthodes publiques au tas, ajoutez-les aussi à l'interface PriorityQueue.

Algorithmes et classes Java.

  • Les classes fournies contiennent une implémentation complète de l'algorithme de Bellman-Ford (trouvez-le).
  • Lancez le sur un trajet de la carte Midi-Pyrénées. C'est lent n'est-ce pas ?
  • Lisez le code Java de Bellman-Ford ; certaines parties vous seront utiles plus tard.
À rendre : diagramme de classes (2)
  • Préparez un deuxième diagramme de classes UML avec les classes du package algo et algo.shortestpath.
  • Soyez synthétiques — n'y mettez pas forcément toutes les classes, et uniquement les méthodes qui vous semblent essentielles.

(Un bon diagramme de classes est un diagramme de classes que l'on a envie de lire.)

L'algorithme de Dijkstra

Vous ne devez pas modifier les classes du package graph.
C'est un principe de séparation des préoccupations : la structure du graphe ne doit pas être modifiée par les algorithmes qui exploitent le graphe.
Vous serez drôlement content d'avoir respecté ce principe quand vous implémenterez le problème final.

Les labels

  • Vous avez besoin d'une nouvelle classe Label (dans le package shortestPath), qui contient
    • sommet courant : sommet associé à ce label (sommet ou numéro de sommet).
    • marque : booléen, vrai lorsque le coût min de ce sommet est définitivement connu par l'algorithme.
    • coût réalisé : valeur courante du plus court chemin depuis l'origine vers le sommet. Pour éviter toute confusion plus tard, ne l'appelez pas simplement coût.
    • père : correspond au sommet précédent sur le chemin correspondant au plus court chemin courant. Afin de reconstruire le chemin à la fin de l'algorithme, mieux vaut stocker l'arc plutôt que seulement le père.
    • Ajoutez les getters.
    • Important pour la suite : une méthode getCost() qui renvoie le coût de ce label. Pour le moment, le coût est égal au coût réalisé.
  • Vous devez aussi pouvoir associer un label à chaque noeud — sans modifier la classe Node ni la classe Graph.
    Notez que les noeuds des graphes sont numérotés de 0 à N-1.

L'algo complet

  • Vous avez maintenant tout ce qu'il faut pour coder un Dijkstra.
  • Pour effectuer des tests simples, regardez la carte carre (c'est un quadrillage).
  • Lorsque l'algorithme fonctionne, testez le trajet INSA -> Bikini. Le trajet suit le canal... qui n'est pas accessible aux voitures. Ça ne va pas.
    Intéressez vous à AbstractInputData.
  • Votre algorithme ne plante pas lorsque l'origine et la destination ne sont pas dans la même composante connexe.
  • StarStarFacultatif Si Dijsktra fonctionne correctement, maintenant comment faire si vous êtes à vélo ?
Questions de compréhension / réflexion :
  • Quelle est la complexité de l'opération add sur le tas ? et de remove ?
  • Et donc, quelle est la complexité théorique de votre Dijkstra ?
  • Cela devrait vous sembler bizarre. La prochaine partie vous aidera à appréhender ce point.

Un observeur pour votre Dijkstra

Observer
  • Trouvez sur internet ce qu'est le Design Pattern Observer (il s'appelle aussi publish-subscribe).
    C'est un grand classique de programmation objet (et pas seulement objet), qui pourrait bien être LE design pattern le plus utile au monde.
  • Allez voir ShortestPathAlgorithm, qui est une classe abstraite dont hérite votre classe DijkstraAlgorithm. Elle contient plusieurs méthodes qui servent à réveiller les observateurs : notifyNodeReached(), etc.
  • Complétez votre algorithme de Dijkstra pour qu'il invoque ces méthodes au moment voulu. Cela aura pour effet de vous permettre de visualiser la progression de l'algorithme sur la carte (sur la vue originale du graphe).

Avez-vous vraiment codé un algorithme de Dijkstra ?

Quelques vérifications de votre implémentation :Doh !
  • Vérification visuelle du comportement de l’algorithme de Dijkstra (afficher sur la carte les sommets explorés au fur et à mesure de leur ajout dans le tas, en principe effectué automatiquement par l’observateur). Est-ce cohérent avec le principe de la méthode ?
  • L'algorithme s'arrête dès qu'il a atteint la destination (au contraire de Bellman-Ford)
  • Vérifier (par un simple affichage temporaire) que le coût des labels marqués est croissant au cours des itérations.
  • Votre algorithme utilise bien la méthode remove du tas - d'une manière ou d'une autre. On ne vous l'a pas fait coder pour rien tout de même.
  • Le PCC en distance et le PCC en temps donnent-ils des résultats (visuels et numériques) cohérents entre eux ?

Vérifications automatiques

Il est temps d'automatiser les tests de validité de votre algorithme.
  • Vous partez de la classe Launch déjà écrite. Si vous êtes hardi, vous pouvez même transformer cette classe en test(s) Junit.
  • Définissez plusieurs scénarios. Chaque scénario est défini par :
    • une carte (tester des cartes routières et non routières)
    • la nature du coût (tester en distance et en temps)
    • une origine et une destination (tester plusieurs valeurs)
    Les scénarios doivent être convaincants et représentatifs des situations pouvant arriver (chemin inexistant, chemin de longueur nulle, trajet court, trajet long et pénible avec des enfants, ...).
  • Sur ces scénarios, vérifier que le chemin construit par votre algo est valide.
  • Vérifiez aussi que le coût du chemin calculé par Dijkstra est bien le même que celui calculé par la classe Path. Depuis la 1A vous savez qu'on ne compare pas deux réels avec ==.
  • Sur les petits scénarios, vérifiez que vous obtenez les mêmes résultats qu'avec Bellman-Ford (que faut-il tester ?)
  • Sur les scénarios plus grands, Bellman-Ford sera inutilisable. Réfléchissez à quelques tests automatiques que vous pouvez tout de même effectuer pour vous rassurer sur le chemin trouvé.
  • Concevez vos tests de manière modulaire : vous les ré-utiliserez pour A-star.

Bilan

  • Votre implémentation du Tas binaire fonctionne (tous les tests JUnit passent).
  • L'algo de PCC implémenté se comporte comme attendu. Tous les résultats semblent cohérents.