Itinéraires et graphes
Introduction
Vous demandez à votre téléphone un itinéraire de chez vous au lycée. En une seconde, il vous propose un trajet, une durée estimée, parfois trois variantes : le plus rapide, le plus court, le plus économe. Comment une machine prend-elle cette décision ? La réponse mêle géographie numérique (cours précédent) et un objet mathématique fondamental en informatique : le graphe.
D'un plan à un graphe
Sur un plan de ville, vous voyez des rues, des intersections, des places, des ronds-points. Un logiciel de calcul d'itinéraire, lui, ne « voit » rien de tout cela. Il manipule une représentation abstraite : le graphe.
Le graphe en deux mots
Un graphe est une collection de sommets (les points) reliés par des arêtes (les liens). C'est tout. Ni plus, ni moins.
Pour transformer un plan en graphe :
- Chaque intersection devient un sommet.
- Chaque tronçon de rue entre deux intersections devient une arête.
Sur ce graphe, trouver un itinéraire entre deux points, c'est trouver une suite d'arêtes qui mène du sommet de départ au sommet d'arrivée.
Sur un graphe représentant une ville, que représente un sommet ?
Pondérer les arêtes
Toutes les rues ne se valent pas. 50 mètres dans une zone piétonne, ce n'est pas la même chose que 50 mètres sur un boulevard à 50 km/h. Pour en tenir compte, on étiquette chaque arête avec un poids : ce poids représente le coût du tronçon — typiquement la durée ou la distance.
| Arête | Distance (m) | Vitesse (km/h) | Durée (s) |
|---|---|---|---|
| A → B | 400 | 50 | 29 |
| B → C | 150 | 30 | 18 |
| A → C | 600 | 50 | 43 |
On obtient un graphe pondéré. La question devient alors : « quelle est la suite d'arêtes qui minimise la somme des poids entre le départ et l'arrivée ? » C'est ce qu'on appelle le plus court chemin.
L'idée du plus court chemin
Imaginons le mini-graphe suivant — quatre points , , , avec leurs durées en minutes :