TP Python – Largeur, chemins et Dijkstra

BTS SIO SISR 2e année – Pour aller plus loin – S17

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – Parcours en largeur

Écris bfs(g, depart) qui renvoie la liste des sommets dans l'ordre du parcours en largeur (avec une deque). Les voisins sont pris dans l'ordre de la liste.

J'anticipe. Reprends la trace de l'exercice 1.

###

Lancer assert bfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "A") == ["A", "B", "C", "D", "E"]bksl-nlassert bfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "C") == ["C", "D", "E", "A", "B"]bksl-nlassert bfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "D") == ["D"]bksl-nlassert bfs({"X": []}, "X") == ["X"]bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

from collections import dequebksl-nlbksl-nlbksl-nldef bfs(g, depart):bksl-nl """Ordre de visite en largeur."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice B – Distances en sauts

Écris distances_bfs(g, depart) qui renvoie un dictionnaire sommet -> nombre de sauts minimal pour les sommets atteignables (le départ est à 0).

J'anticipe. Écris les distances de l'exercice 2.

###

Lancer assert distancespy-undbfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "A") == {"A": 0, "B": 1, "C": 1, "D": 2, "E": 2}bksl-nlassert distancespy-undbfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "D") == {"D": 0}bksl-nlassert distancespy-undbfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "E") == {"E": 0, "A": 1, "B": 2, "C": 2, "D": 3}bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

from collections import dequebksl-nlbksl-nlbksl-nldef distancespy-undbfs(g, depart):bksl-nl """Dictionnaire sommet -> nombre minimal de sauts."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice C – Chemin le plus court en sauts

Écris chemin_bfs(g, a, b) qui renvoie la liste des sommets d'un plus court chemin de a à b (en nombre de sauts), ou None si b n'est pas atteignable. Mémorise le parent de chaque sommet.

###

Lancer assert cheminpy-undbfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "A", "D") == ["A", "B", "D"]bksl-nlassert cheminpy-undbfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "A", "E") == ["A", "C", "E"]bksl-nlassert cheminpy-undbfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "A", "A") == ["A"]bksl-nlassert cheminpy-undbfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "D", "A") == Nonebksl-nlassert cheminpy-undbfs({"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": ["A"]}, "E", "D") == ["E", "A", "B", "D"]bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

from collections import dequebksl-nlbksl-nlbksl-nldef cheminpy-undbfs(g, a, b):bksl-nl """Plus court chemin (liste de sommets) ou None."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Pourquoi remonte-t-on du but vers le départ ?

Exercice D – Dijkstra

Écris dijkstra(g, depart) pour un graphe pondéré (poids positifs ou nuls) : renvoie un dictionnaire sommet -> distance minimale pour les sommets atteignables. Utilise heapq.

J'anticipe. Reprends les traces du cours et de l'exercice 4.

###

Lancer assert dijkstra({"A": {"B": 4, "C": 1}, "B": {"D": 1}, "C": {"B": 2, "D": 5}, "D": {}}, "A") == {"A": 0, "C": 1, "B": 3, "D": 4}bksl-nlassert dijkstra({"S": {"A": 7, "B": 2}, "A": {"C": 1}, "B": {"A": 3, "C": 8}, "C": {}}, "S") == {"S": 0, "B": 2, "A": 5, "C": 6}bksl-nlassert dijkstra({"A": {"B": 4, "C": 1}, "B": {"D": 1}, "C": {"B": 2, "D": 5}, "D": {}}, "D") == {"D": 0}bksl-nlassert dijkstra({"X": {}}, "X") == {"X": 0}bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

import heapqbksl-nlbksl-nlbksl-nldef dijkstra(g, depart):bksl-nl """Dictionnaire sommet -> distance minimale."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice E – Dijkstra avec chemin

Écris chemin_dijkstra(g, a, b) qui renvoie (distance, chemin) pour un plus court chemin pondéré de a à b, ou None si b n'est pas atteignable. Mémorise les parents lors de chaque amélioration.

###

Lancer assert cheminpy-unddijkstra({"A": {"B": 4, "C": 1}, "B": {"D": 1}, "C": {"B": 2, "D": 5}, "D": {}}, "A", "D") == (4, ["A", "C", "B", "D"])bksl-nlassert cheminpy-unddijkstra({"S": {"A": 7, "B": 2}, "A": {"C": 1}, "B": {"A": 3, "C": 8}, "C": {}}, "S", "C") == (6, ["S", "B", "A", "C"])bksl-nlassert cheminpy-unddijkstra({"A": {"B": 4, "C": 1}, "B": {"D": 1}, "C": {"B": 2, "D": 5}, "D": {}}, "A", "A") == (0, ["A"])bksl-nlassert cheminpy-unddijkstra({"A": {"B": 4, "C": 1}, "B": {"D": 1}, "C": {"B": 2, "D": 5}, "D": {}}, "D", "A") == Nonebksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

import heapqbksl-nlbksl-nlbksl-nldef cheminpy-unddijkstra(g, a, b):bksl-nl """(distance, chemin) ou None."""bksl-nl ...bksl-nlbksl-nl

---

---