Important ! On travaille ici sur des graphes non pondérés. Veillez donc à régler le paramètre “–mud_density 0″.
Parcours en largeur
Programmer le parcours en largeur en vous inspirant du pseudocode vu en cours.
Notez que votre fonction de parcours en largeur a besoin en arguments du graphe et d’un sommet de départ.
Routage
Afin de retrouver un chemin le plus court pour atteindre un bout de fromage à partir de l’exécution du parcours en largeur, il va falloir utiliser l’algorithme de routage.
Dans votre fonction de parcours en largeur, retenez quel sommet a permi d’ajouter quel autre pour retrouver le chemin le plus court.
Maintenant, proposez une fonction qui retrouve le chemin le plus court à partir d’un tableau de routage, d’un sommet initial et d’un sommet d’arrivée.
Quoi faire ensuite ?
Les résultats obtenus en suivant ce TP seront présentés lors de l’entretien de la séance 3.
Ramassez un morceau de fromage dans un labyrinthe non pondéré en utilisant un chemin le plus court.
Tracez l’influence de la taille du labyrinthe sur la longueur du chemin le plus court.
Allez plus loin !