Le bus le plus rapide
Pour aller de chez toi au stade, tu peux prendre deux bus ou trois bus. Deux bus, c'est moins de changements. Mais est-ce le plus rapide ?
Pas toujours. Un seul trajet peut durer 20 minutes, et trois petits trajets seulement 8 minutes en tout.
Pour choisir, il faut compter les minutes, pas les arrêts. On met donc un nombre sur chaque arête.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Graphe pondéré | Un graphe où chaque arête porte un nombre, par exemple des minutes. | Maison à Parc : 2 minutes |
| Poids | Le nombre écrit sur une arête. | 2 |
| Trajet le plus court | Le trajet qui a le plus petit total de poids. Ce n'est pas toujours celui qui a le moins d’arêtes. | Maison, Parc, Gare, Stade : 8 minutes |
| Lieu fixé | Un lieu dont on connaît le meilleur temps. Il ne changera plus. | Le départ, à 0 minute |
| Mise à jour | Remplacer un temps par un temps plus petit qu'on vient de trouver. | Gare passe de 4 à 3 minutes |
| Dijkstra | Le nom d'un informaticien et de sa méthode pour trouver le trajet le plus court. | On fixe toujours le lieu le plus proche |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : lire le réseau
À toi de jouer
À toi : lire le réseau
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Le parcours en largeur ne suffit plus
Le parcours en largeur compte les arêtes. Pour aller de Maison à Stade, il trouve Maison, Gare, Stade : deux arêtes, mais 9 minutes.
Le trajet Maison, Parc, Gare, Stade a trois arêtes, mais seulement 8 minutes. Il est plus court en temps. Il faut une autre méthode.
L'idée : un carnet de temps
On note dans un carnet le meilleur temps connu pour chaque lieu. Au départ : 0 pour le départ, et « inconnu » pour les autres.
On répète : on choisit le lieu pas encore fixé qui a le plus petit temps, et on le fixe. Puis on regarde ses voisins : si passer par lui est plus rapide, on met leur temps à jour.
Exemple travaillé : les temps depuis Maison
| Étape | On fixe | Maison | Parc | Gare | Stade |
|---|---|---|---|---|---|
| Départ | - | 0 | inconnu | inconnu | inconnu |
| 1 | Maison (0) | 0 fixé | 2 | 4 | inconnu |
| 2 | Parc (2) | 0 | 2 fixé | 3 | 9 |
| 3 | Gare (3) | 0 | 2 | 3 fixé | 8 |
| 4 | Stade (8) | 0 | 2 | 3 | 8 fixé |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : lire les étapes
À toi de jouer
À toi : lire les étapes
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.