Calcul d'itinéraires
Comprendre comment les applications GPS calculent le meilleur chemin : graphes, pondération et algorithme de Dijkstra.
Comprendre comment fonctionne un calcul d'itinéraire
Modéliser un réseau routier sous forme de graphe
Appliquer l'algorithme de Dijkstra sur un exemple simple
Comparer les résultats de différents services GPS
Le calcul d'itinéraire numérique
Un des atouts majeurs de la cartographie numérique est de permettre des calculs d'itinéraires à partir des données enregistrées sur des cartes vectorielles.
Applications et services courants
Comparer les services GPS
Pour aller du lycée Nelson Mandela (14 rue Louis Reybaud, 13012 Marseille) au lycée Félix Esclangon (32 bd Louis Martin Bret, 04100 Manosque), voici ce que donnent les différents services :
| Service | Temps estimé | Distance |
|---|---|---|
| 🏛️ Géoportail | 59 min | 91,4 km |
| 📍 Mappy | 1h06 | 91 km |
| 🚗 ViaMichelin | 1h09 | 90 km |
| 🗺️ Google Maps | 1h06 | 90,9 km |
Calculez le même itinéraire sur Géoportail, Mappy, ViaMichelin et Google Maps.
- Relevez la distance et le temps pour chaque service.
- Que remarquez-vous ? Les itinéraires proposés sont-ils identiques ?
- Comment expliquer les différences de temps alors que les distances sont proches ?
- Quel service vous semble le plus fiable ? Justifiez.
Modéliser un réseau routier : les graphes
Pour calculer un itinéraire, le réseau routier est modélisé sous forme de graphe — une structure mathématique composée de :
Arêtes : les routes ou segments reliant deux nœuds.
Pondérations : les valeurs associées aux arêtes (distance en km, durée en minutes, coût en €…).
Exemple de graphe routier – les chiffres représentent des distances en km
Ce modèle mathématique permet à un algorithme de calculer automatiquement le chemin le plus court (ou le plus rapide) entre deux points.
L'algorithme de Dijkstra
Principe de fonctionnement
L'algorithme fonctionne de façon gloutonne : à chaque étape, il visite le nœud non encore traité dont la distance depuis le départ est la plus faible, et met à jour les distances de ses voisins si un meilleur chemin est trouvé.
- Initialiser toutes les distances à l'infini (∞), sauf le départ (distance = 0)
- Choisir le nœud non visité avec la plus petite distance connue
- Pour chaque voisin de ce nœud, calculer la distance totale via ce nœud
- Si elle est plus courte que la distance connue, la mettre à jour
- Marquer le nœud comme visité et répéter jusqu'à atteindre la destination
Sur le graphe illustré ci-dessus, trouvez le chemin le plus court de A à F.
- Listez tous les chemins possibles de A à F avec leurs distances totales.
- Appliquez l'algorithme de Dijkstra pas-à-pas (suivez la fiche d'activité).
- Quel est le chemin le plus court ? Quelle est sa longueur totale ?
Bilan du chapitre
| Notion | Définition |
|---|---|
| Graphe | Structure mathématique modélisant un réseau : nœuds reliés par des arêtes |
| Nœud (sommet) | Point du graphe représentant une ville, un carrefour, une intersection |
| Arête | Lien entre deux nœuds représentant une route ou un segment |
| Pondération | Valeur associée à une arête (distance, durée, coût…) |
| Algorithme de Dijkstra | Algorithme trouvant le plus court chemin dans un graphe pondéré (E. Dijkstra, 1959) |
| Carte vectorielle | Représentation numérique du réseau routier permettant les calculs d'itinéraire |