SNT · Seconde · Cartographier
Calcul d’itinéraire
Un GPS parcourt un graphe, pas une carte.
En bref
Un calculateur d'itinéraire ne regarde pas une carte : il parcourt un graphe.
Modéliser la route
| L'élément du graphe | Ce qu'il représente |
|---|---|
| Le sommet | Une intersection |
| L'arête | Un tronçon de route |
| Le poids | Ce que l'on cherche à minimiser |
| Le poids choisi | Ce qu'il donne |
|---|---|
| La distance | Le trajet le plus court |
| La durée | Le plus rapide — vitesse autorisée, type de voie, feux, trafic en temps réel |
| Un coût composite | Péages, pente, interdictions de tourner |
Changer le poids change l'itinéraire : le plus court n'est pas le plus rapide.
L'algorithme de Dijkstra
| Le point | Son contenu |
|---|---|
| Sa date | 1959 |
| Ce qu'il calcule | Le plus court chemin d'un sommet vers tous les autres |
| Sa méthode | Il part de l'origine, explore les sommets les plus proches, met à jour les distances |
| Sa condition | Les poids doivent être positifs |
Un GPS ne cherche pas la belle route : il minimise une quantité qu'on lui a demandé de minimiser.
Aller plus vite
| L'amélioration | Son principe |
|---|---|
| L'algorithme A étoile | Il ajoute une estimation de la distance restante — le vol d'oiseau — pour explorer d'abord dans la bonne direction |
| Les prétraitements | Ils hiérarchisent le réseau : les autoroutes d'abord |
Sur un réseau de millions de sommets, Dijkstra seul explore trop.
Les données et leurs effets
| La donnée | Sa source |
|---|---|
| Le fond de carte | OpenStreetMap ou des fournisseurs privés |
| Le trafic | Les téléphones des utilisateurs eux-mêmes |
Le calcul d'itinéraire a des effets réels sur le terrain : reporter le trafic dans des rues résidentielles, faire disparaître un commerce d'un trajet, ou saturer une déviation que tout le monde emprunte au même moment.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Comment un réseau routier est-il modélisé pour un calcul d’itinéraire ?
2.Que peut représenter le poids d’une arête ?
3.Que calcule l’algorithme de Dijkstra ?
4.En quelle année l’algorithme de Dijkstra a-t-il été publié ?
5.Qu’apporte l’algorithme A étoile par rapport à Dijkstra ?
6.Le trajet le plus court en distance est toujours le plus rapide.
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Calcul d’itinéraire » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
