L’algorithme du plus court chemin de Dijkstra¶
Activité collaborative et débranchée pour introduire l’algorithme du plus court de chemin de Dijkstra.
Informations techniques
⏳ : 2 périodes
🔌 : débranché
📕 : algorithmique
💡 : découvrir l’algorithme de Dijkstra, son utilité, son fonctionnement
🔧 : connexion internet pour la mise en situation
Déroulement
Mise en situation générale (5 min) pour comprendre un contexte de la vie quotidienne dans lequel cet algorithme est utilisé et qui constituera un fil rouge concret tout au long de l’activité.
Mise en situation spécifique (15 min) pour passer à un niveau d’abstraction et de généralisation plus élévé.
Identification du problème (5 min), identification de l’objectif, explication de la non-trivialité du problème.
Découverte (15 min) par essais-erreurs de l’algorithme et de sa justification par simulation humaine.
Formalisation (10 min) de l’algorithme.
Exemples d’utilisation (15 min) de l’algorithme et exercices.
Réflexions plus approfondie sur l’algorithme pour aller plus loin.
1. Mise en situation générale¶
L’enseignant va sur une page de navigation (p.ex OpenStreetMap) et montre un exemple de requête de chemin pour relier deux points.
Comment le site web a-t-il déterminé le chemin qu’il nous indique ?
Quelles données a-t-il à sa disposition pour déterminer ce chemin ?
Tout le réseau routier est représenté sous forme d’un graphe.
Les croisements et embranchements sont représentés par les sommets du graphe et les routes qui les relient sont représentées par les arêtes du graphe.
2. Mise en situation spécifique¶
L’enseignant distribue à chaque élève un graphe suffisamment compliqué dans lequels la longueur des arêtes est indiquée. Ils doivent trouver, individuellement, le plus court chemin reliant deux points. Le graphe est tel qu’il y a plusieurs plus courts chemins.
Mise en commun
Qui a trouvé le plus court chemin ?
Etes-vous sûr qu’il s’agit du plus court chemin? Le cas échéant, comment le savez-vous ?
Chacun donne son plus court chemin.
Y a-t-il des chemins plus courts que ça ?
Dans un voyage en voiture, on ne veut pas forcément le plus court chemin, mais souvent le plus rapide.
Par exemple, on va prendre l’autoroute de contournement de Lausanne qui est plus longue, mais plus rapide que de traverser la ville.
On retrouve le même graphe qu’avant, mais cette fois on a le temps de parcours entre chaque point qui est indiqué et on ne peut plus se baser sur les aspects géométriques pour trouver le plus courts chemin.
Mise en commun
Qui a trouvé le plus court chemin ?
Etes-vous sûr qu’il s’agit du plus court chemin? Le cas échéant, comment le savez-vous ?
Chacun-e donne son plus court chemin.
Y a-t-il des chemins plus courts que ça ?
Que faut-il faire pour être sûr-e que ce soit vraiment le plus court ?
3. Identification du problème¶
Le problème est donc donnée sous forme d’un graphe constitué de sommets reliés par des arêtes qui ont une certaine longueur. Dans le cas ci-desssus, les sommets représentent des villes, les arêtes les routes, et les longueurs la durée du trajet. La longueur totale est donnée par la somme des longueurs des arêtes empruntée.
4. Découverte¶
🎲 Activité
Pour déterminer le plus court chemin dans ce graphe, la classe va le faire tous ensemble. Chaque élève représente un sommet et reçoit le sous-graphe constitué de son sommet et ses voisins directs (autrement dit une liste de ses voisins et les distances correspondantes). Chaque élève prend en outre une feuille avec un crayon et une gomme.
Déroulement
L’enseignant délimite la classe en trois zones:
La zone A, contenant les sommets qui ont trouvé la longueur du chemin le plus court depuis le sommet de départ.
La zone B, contenant les sommets qui ont trouvé une longueur de chemin depuis le sommet de départ, mais pas forcément la plus petite.
La zone C, contenant les sommets qui n’ont pas trouvé de longueur depuis le sommet de départ.
Les instructions pour les élèves sont les suivantes:
Les élèves commencent tous dans la zone C.
Lorsqu’une élève se rend compte qu’elle peut calculer la longueur d’un chemin depuis le sommet de départ, elle écrit sur sa feuille par quel voisin ce chemin passe ainsi que la distance correspondante, et se place dans la zone B.
Les élèves de la zone B peuvent se voir mutuellement leur feuille
Lorsqu’une élève de la zone B se rend compte qu’il existe un chemin plus court que la longueur indiquée sur sa feuille, elle met sa feuille à jour.
Lorsqu’une élève se rend compte que le chemin indiqué sur sa feuille est le plus court, elle passe dans la zone A.
Dans la zone A, toutes les feuilles sont clairement visibles.
Si tout se passe bien, les élèves vont se déplacer dans les zones B et C en commençant par le sommet de départ. Idéalement, elles doivent se rendre compte des principes de base de l’alogrithme de Dijkstra:
Si un de leur voisin direct a trouvé une longueur de chemin, il ont également une longueur de chemin en ajoutant la distance qui les sépare.
Si une élève a le chemin de plus court de la zone B et que personne ne s’y ajoute (i.e. tous les voisin des personnes dans la zone A sont soit dans la zone A soit dans la zone B), elle peut passer en zone A.
A la fin, en suivant les relations de voisinage, on peut reconstituer le chemin le plus court.
Attention
Cette activité implémente dans les faits une version distribuée de l’algorithme où les sommets peuvent changer de zone en parallèle. Il est conseillé de bien marquer la transition à l’algorithme séquentiel.
5. Formalisation¶
L’enseignant formalise l’algorithme au tableau avec l’aide des élèves. Pour aider à la compréhension et à la représentation, il peut utiliser des couleurs pour dénommer les zones et ainsi pouvoir changer les sommets de zone en modifiant la couleur (ou en utilisant un autre moyen graphique). Ici la zone A est “rouge”, la zone B est “verte” et la zone C est “blanche” (non marquée).
Formalisation
Mettre le sommet de départ (S) en rouge, sa distance au sommet de départ est 0.
Mettre en vert tous les sommets voisins de ce sommet (S) qui sont en blanc et indiquer en vert leur distance au sommet de départ en passant par ce sommet S et indiquer le chemin à ce sommet S par une flèche verte.
Vérifier tous les voisins de ce sommet (S) qui sont en vert si leur distance au sommet de départ est plus petite en passant par ce sommet. Si c’est le cas ajuster leur distance au sommet de départ et leur flèche pour qu’elle pointe vers le sommet S.
Prendre le sommet vert avec la plus petite distance au sommet de départ et le mettre en rouge avec sa distance et sa flèche. Ce sommet est le nouveau sommet S.
Si ce sommet S est le sommet d’arrivée, le plus court chemin est obtenu en suivant les flèches, sinon retourner au point 2.
6. Exemples d’utilisation¶
L’enseignant fait un exemple au tableau avec les élèves et leur propose ensuite d’essayer seuls ou par deux sur des graphes donnés.
Ce jeu consiste à trouver une manière de relier deux mots ayant le même nombre de lettres (par exemple VERSE et LITRE) avec une série de mots existants dont chaque mot ne diffère du précédent que d’une seule lettre. Dans notre exemple, une solution est donnée par :
VERSE - VERRE - SERRE - SEVRE - LEVRE - LIVRE - LITRE
On suppose disposer d’une liste de tous les mots de la langue française.
Comment l’algorithme du plus cours chemin peut-il être utilisé pour trouver une solution à ce jeu ? En particulier, quel graphe serait-il nécessaire de construire, à quoi correspondrait ses nœuds et ses arêtes et ses distances ?
Selon le niveau atteint en programmation, une petite application proposant ce jeu et les solutions correspondantes pourrait être programmée par exemple en utilisant une libraire de graphe telle que igraph ou networkX en python.
L’autre jour, vous avez flashé sur quelqu’un que vous ne connaissez pas mais dont vous avez réussi à obtenir le nom. Après avoir passé beaucoup de temps sur son profil dans votre réseau social préféré, vous recevez une notification vous indiquant quel ami-e pourra sans doute vous aider à vous rapprocher de cette personne. Comme ce réseau social a-t-il pu utiliser l’algorithme de Dijkstra pour vous faire cette recommandation?