Recherche du plus court chemin dans un graphe
Les graphes sont utilisés pour modéliser des informations liées.
L'activité proposée repose sur la recherche dans un réseau routier du plus court chemin entre deux points. Un problème bien classique et utilisé régulièrement lorsque l'on veut se rendre sur un lieu donné avec notre smartphone ou autre navigateur GPS.
Il s'agit de modéliser le problème à l'aide d'un graphe, puis de rechercher toutes les chaînes élémentaires de ce graphe avec le sommet de départ et d'arrivée imposés.
On fournit aux élèves un bonne partie du programme qui est basé sur un algorithme classique de FDS qui utilise la récursivité.
Les élèves ont a compléter le programme pour le faire fonctionner.
Ils commenceront pas afficher toutes les chaînes possibles, puis ils rechercheront la chaîne de poids minimal à l'aide d'algorithme de recherche de minimum assez classique.
Manifestement cette notion de graphes n'est vue qu'en spé maths en T ES uniquement en mathématiques.
Un article indique que la notion de graphe pourrait être initiée au collège, à méditer...
http://irem.univ-reunion.fr/spip.php?article576