Le plus court chemin

I. Le plus court chemin

Note

🤔 Comment est-on sûr qu'un chemin va être trouvé entre deux sommets A et B ?

Si le graphe est connexe, tout parcours en largeur au départ de A va parcourir l'intégralité du graphe, et donc passera par B à un moment. Un chemin sera donc forcément trouvé entre A et B.

🤔 Comment est-on sûr que ce chemin trouvé est le plus court ?

Dans un parcours en largeur, on visite d’abord le sommet origine, puis la génération des sommets qui sont à distance 1 (en nombre d’arêtes), puis la génération des sommets qui sont à distance 2, etc. Quant on visite le point d’arrivée, le numéro de sa génération représente le nombre d’arêtes qui le séparent du point de départ. Autrement dit, un parcours en largeur à partir du sommet d’origine permet de trouver un plus court chemin vers le sommet d’arrivée en nombre d’étapes (c’est-à-dire d’arêtes traversées). Si on prend la précaution de noter (dans un dictionnaire parents) le père de chaque génération de sommets, il suffit de remonter de père en père pour reconstituer le chemin d’accès du point d’arrivée.

À vous

Compléter le script ci-dessous :

Graphe du test :

###

Lancer # Testsbksl-nlmonpy-undgraphe = {"A":["B", "C"], "B":["A", "D", "E"], "C":["A", "D"],bksl-nl"D":["B", "C", "E"], "E":["B", "D", "F", "G"], "F":["E", "G"], "G":["E", "F", "H"],bksl-nl"H":["G"]}bksl-nlbksl-nlassert recherchepy-undchemin(monpy-undgraphe, "A", "G") == ["A", "B", "E", "G"]bksl-nlbksl-nl# Autres testsbksl-nlassert recherchepy-undchemin(monpy-undgraphe, "H", "C") == ["H", "G", "E", "D", "C"]bksl-nlassert recherchepy-undchemin(monpy-undgraphe, "H", "M") == []bksl-nlassert recherchepy-undchemin(monpy-undgraphe, "D", "H") == ["D", "E", "G", "H"]bksl-nlassert recherchepy-undchemin(monpy-undgraphe, "D", "D") == ["D"]bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def recherchepy-undchemin(graphe, depart, arrivee): bksl-nl parents = {depart: None}bksl-nl file = [depart]bksl-nl while file != []:bksl-nl sommet = ...bksl-nl if sommet == arrivee:bksl-nl ... bksl-nl for voisin in graphe[sommet]:bksl-nl if ... not in ...:bksl-nl file.append(...) bksl-nl parents[...] = ...bksl-nl return []bksl-nlbksl-nlbksl-nldef remontepy-undchemin(depart, arrivee, parents):bksl-nl sommet = arriveebksl-nl chemin = [arrivee]bksl-nl while sommet != depart:bksl-nl sommet = parents[...]bksl-nl chemin = ... + ...bksl-nl return cheminbksl-nlbksl-nl# Testbksl-nlmonpy-undgraphe = {"A":["B", "C"], "B":["A", "D", "E"], "C":["A", "D"],bksl-nl"D":["B", "C", "E"], "E":["B", "D", "F", "G"], "F":["E", "G"], "G":["E", "F", "H"],bksl-nl"H":["G"]}bksl-nlbksl-nlassert recherchepy-undchemin(monpy-undgraphe, "A", "G") == ["A", "B", "E", "G"]bksl-nlbksl-nldef recherchepy-undchemin(graphe, depart, arrivee): bksl-nl parents = {depart: None}bksl-nl file = [depart]bksl-nl while file != []:bksl-nl sommet = file.pop(0)bksl-nl if sommet == arrivee:bksl-nl return remontepy-undchemin(depart, arrivee, parents) bksl-nl for voisin in graphe[sommet]:bksl-nl if voisin not in parents:bksl-nl file.append(voisin) bksl-nl parents[voisin] = sommetbksl-nl return []bksl-nlbksl-nldef remontepy-undchemin(depart, arrivee, parents):bksl-nl sommet = arriveebksl-nl chemin = [arrivee]bksl-nl while sommet != depart:bksl-nl sommet = parents[sommet]bksl-nl chemin = [sommet] + cheminbksl-nl return cheminbksl-nlbksl-nl

---

---

II. Remarques

Retour sur l'efficacité

• Pour une question de simplification des codes, Nous avons utilisé ma_liste.pop(0).
  👉 Pour pallier à ce problème, nous pouvons utiliser le deque du module collections documentation deque

• Nous avons aussi utilisé une concaténation de liste à gauche. C'est également très coûteux, à cause de tous les décalages qu'il faut effectuer dans la liste à chaque fois qu'on ajoute un élément à gauche.
  👉 il vaut mieux créer la TAD file avec une liste chaînée compléments TAD

III. Crédits

Romain Janvier, Gilles Lassus, Eduscol, Nicolas Revéret