Le trajet qui passe par le moins d’arrêts
Le parcours en largeur explore un graphe en visitant d’abord les sommets les plus proches du départ. Il trouve le chemin qui passe par le moins d’arêtes, et il sert aux plans de transport, aux réseaux d’amis et aux sites web.
Un plan de tramway est un graphe : les arrêts sont des points, les lignes qui les relient sont des traits. Pour aller de la gare au stade, on veut passer par le moins d’arrêts possible.
À la fin de cette leçon
Remarque
Je peux trouver un chemin avec le parcours en largeur.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Graphe | des sommets reliés par des arêtes | |
| Sommet | un point du graphe | un arrêt de tramway |
| Arête | un lien entre deux sommets | une ligne entre deux arrêts |
| File | une liste où le premier arrivé est le premier sorti | |
| Parcours en largeur | explorer d’abord les sommets les plus proches du départ | |
| Sommet visité | un sommet déjà rencontré, qu’on ne remet pas dans la file |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un graphe se range dans un dictionnaire
Un graphe est un ensemble de sommets reliés par des arêtes. En Python, on le range dans un dictionnaire : chaque sommet a pour valeur la liste de ses voisins.
Dans notre réseau de tramway, Gare a deux voisins : Mairie et Marche. Un trajet est une suite de sommets où chacun est voisin du précédent.
Le parcours en largeur utilise une file
On part du sommet de départ avec une distance de 0. On le met dans une file, où le premier arrivé est le premier sorti.
À chaque tour, on sort un sommet de la file. On met ses voisins non visités dans la file, avec la distance du sommet plus 1. Les sommets proches sortent donc avant les lointains.
Le parcours en largeur du tramway
# Les arrêts les plus proches d’abord, grâce à une file.
reseau = {
"Gare": ["Mairie", "Marche"],
"Mairie": ["Gare", "Universite", "Parc"],
"Marche": ["Gare", "Parc"],
"Universite": ["Mairie", "Stade"],
"Parc": ["Mairie", "Marche", "Stade"],
"Stade": ["Universite", "Parc"],
}
distance = {"Gare": 0} # les arrêts déjà visités, avec leur distance
file = ["Gare"]
while len(file) > 0:
arret = file.pop(0) # le premier arrivé, le premier sorti
for voisin in reseau[arret]:
if voisin not in distance:
distance[voisin] = distance[arret] + 1
file.append(voisin)
print(distance)
# Partez de "Stade" : changez les deux mentions de "Gare".
Exemple travaillé : la file depuis Gare
| Tour | Arrêt sorti | Arrêts ajoutés | File après |
|---|---|---|---|
| 1 | Gare | Mairie, Marche | Mairie, Marche |
| 2 | Mairie | Universite, Parc | Marche, Universite, Parc |
| 3 | Marche | aucun, Gare et Parc déjà vus | Universite, Parc |
| 4 | Universite | Stade | Parc, Stade |
| 5 | Parc | aucun | Stade |
| 6 | Stade | aucun | vide |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une file sort le premier arrivé
python3 -c "exec('file = [1, 2, 3]\nfile.append(4)\nprint(file.pop(0), file)')"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une pile sort le dernier arrivé
python3 -c "exec('pile = [1, 2, 3]\npile.append(4)\nprint(pile.pop(), pile)')"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Les distances depuis Gare
python3 -c "exec('reseau = {\'Gare\': [\'Mairie\', \'Marche\'], \'Mairie\': [\'Gare\', \'Universite\', \'Parc\'], \'Marche\': [\'Gare\', \'Parc\'], \'Universite\': [\'Mairie\', \'Stade\'], \'Parc\': [\'Mairie\', \'Marche\', \'Stade\'], \'Stade\': [\'Universite\', \'Parc\']}\nd = {\'Gare\': 0}\nf = [\'Gare\']\nwhile len(f) > 0:\n s = f.pop(0)\n for v in reseau[s]:\n if v not in d:\n d[v] = d[s] + 1\n f.append(v)\nprint(d)')"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Les arrêts ne sont pas les minutes
Le parcours en largeur compte les arêtes : il trouve le trajet qui passe par le moins d’arrêts. Il ne sait rien des durées.
Pour le trajet le moins cher ou le plus court en minutes, il faut donner un poids à chaque arête. L’algorithme de Dijkstra prolonge alors la même idée, avec un ordre d’exploration différent.
Trois trajets de la gare au stade
| Trajet | Arrêts | Minutes |
|---|---|---|
| Gare, Mairie, Universite, Stade | 3 | 27 |
| Gare, Marche, Parc, Stade | 3 | 19 |
| Gare, Mairie, Parc, Stade | 3 | 31 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Erreur fréquente
Attention
Beaucoup pensent que le parcours en largeur donne le trajet le plus rapide. Il donne le trajet qui compte le moins d’arrêts, et plusieurs trajets peuvent être à égalité. Pour comparer des minutes ou des prix, il faut des poids sur les arêtes.