# Labyrinthe - distance (BFS)
## 🎯 Objectif
Mettre en œuvre un parcours en largeur (**BFS**) pour calculer la **distance minimale** (nombre d’arêtes / de déplacements) entre deux sommets d’un graphe représentant un **labyrinthe**.
## 📄 Énoncé
On considère un **graphe** `D` (dictionnaire d’adjacence) représentant un labyrinthe :
- chaque sommet est une case (ou un identifiant de case),
- `D[u]` contient la liste des voisins accessibles depuis `u`.
On souhaite Ă©crire une fonction `distance(D, debut, fin)` qui :
- explore le graphe Ă partir de `debut`,
- calcule pour chaque sommet atteint sa distance Ă `debut`,
- renvoie la distance minimale pour atteindre `fin` si `fin` est atteignable,
- sinon renvoie `False`.
👉 L’algorithme attendu est un **BFS** (file d’exploration), qui garantit une distance minimale dans un graphe non pondéré.
## 🧩 Travail demandé
1. Implémenter la fonction `distance(D, debut, fin)` en suivant l’approche BFS.
2. Tester la fonction sur plusieurs couples (`debut`, `fin`) :
- un cas oĂą `fin` est atteignable,
- un cas oĂą `fin` est inatteignable.
3. Vérifier que les distances calculées sont cohérentes (progression par +1).
4. (Bonus) Modifier l’algorithme pour reconstruire un **chemin** (pas seulement la distance).
## đź“Ž Support de travail
- 💾 **Notebook – Labyrinthe : plus court chemin**
đź”— [ressource](https://github.com/unilasalle-apex/Python/blob/main/Labyrinthe_Plus_court_chemin.ipynb)
## ✅ Corrigé
>[!tip]- Corrigé (masqué)
>```python
>def distance(D, debut, fin):
> couleur = dict()
> for x in D:
> couleur[x] = 'green'
> P = {debut : 0}
> couleur[debut] = 'orange'
> Q = [debut]
> while Q:
> u = Q[0]
> for v in D[u]:
> if couleur[v] == 'green':
> P[v] = P[u] + 1
> couleur[v] = 'orange'
> Q.append(v)
> Q.pop(0)
> couleur[u] = 'red'
> if fin in P:
> return P[fin]
> else:
> return False
>```
## 🧠À retenir
- Un parcours **BFS** explore le graphe **par couches** : distance 0, puis 1, puis 2, etc.
- Dans un graphe **non pondéré**, BFS permet d’obtenir la **distance minimale**.
- Le code utilise un système de **couleurs** :
- `green` : non visité,
- `orange` : découvert (dans la file),
- `red` : traité.
## 🗓️ Historique
- **Créé le :** 05 février 2026
- **Auteur :** [[Julien DUQUENNOY]]