Comment Google Maps trouve-t-il un chemin parmi des millions de possibilités ?
Il n'essaie pas tous les chemins : il en ignore l'immense majorité sans jamais les regarder, et c'est ce qui le rend rapide.
Deux secondes plus tard, une ligne bleue s'affiche.
Entre les deux : des milliers d'intersections, et bien plus de trajets envisageables.
Les énumérer un par un serait déraisonnable.
Même idée derrière : navigation GPS, livraison, VTC, transports en commun, acheminement des données sur Internet, secours d'urgence, robots d'entrepôt etc.
LA SEULE FORMULE
Coût d'un chemin = somme des coûts des routes qui le composent.
Un sommet, c'est une intersection.
Une arête, c'est une route reliant deux intersections.
Le coût, c'est le nombre que tu décides de minimiser : minutes, kilomètres, litres, francs.
UN CALCUL QUE TU PEUX REFAIRE
Hypothèses : réseau fictif de quatre lieux, coûts en minutes, fixes, arrondis. On ignore feux, sens interdits et trafic.
A–B : 4 / A–C : 6 / B–C : 1 / B–D : 7 / C–D : 3
A → B → D : 4 + 7 = 11
A → C → D : 6 + 3 = 9
A → B → C → D : 4 + 1 + 3 = 8
Le minimum est 8 minutes. Et c'est le trajet qui compte le plus d'étapes : « moins d'étapes, plus rapide » est une intuition, pas une règle.
Dijkstra trouve la même réponse sans écrire cette liste.
Départ A, coût 0. Voisins : B = 4, C = 6.
On traite le plus petit, B. Par B, C tombe à 4 + 1 = 5, mieux que 6. D apparaît à 4 + 7 = 11.
On traite C (5). Par C, D tombe à 5 + 3 = 8.
On traite D (
, et c'est fini.
Trois sommets examinés, zéro chemin énuméré.
L'image juste : verse de l'eau en A. Elle avance dans toutes les rues à la même vitesse. L'instant où elle atteint D, tu tiens le minimum.
Voilà la mécanique. Ce dont on parle beaucoup moins commence au mot « coût ».
UNE VILLE DEVIENT UN GRAPHE
Une ville n'est plus une carte : c'est un ensemble de points reliés par des liens portant un nombre.
Change ce que le nombre représente, tu changes de problème sans changer de méthode.
« LE PLUS COURT » ET « LE PLUS RAPIDE » SONT DEUX QUESTIONS
Une route de 5 km peut prendre 25 minutes. Une autre de 7 km, 15 minutes.
Minimise les kilomètres : la première gagne. Minimise les minutes : la seconde gagne.
Aucune des deux réponses n'est fausse. Elles ne répondent pas à la même question.
POURQUOI ÇA MARCHE : LES MORCEAUX D'UN BON CHEMIN SONT BONS
Si le meilleur trajet de A à D passe par C, alors le morceau A→C est déjà le meilleur trajet de A à C.
Sinon, tu le remplacerais par un meilleur et le total baisserait. Contradiction.
Donc inutile de retenir plusieurs façons d'arriver à C : une seule suffit, la meilleure.
C'est cette propriété qui autorise à jeter des millions de chemins sans les calculer.
LE TRAFIC NE CHANGE PAS LA CARTE, IL CHANGE LES POIDS
Google Maps Platform documente trois modèles de trafic. Sur son exemple de trajet :
- optimiste : 1 238 secondes, soit 20 min 38 s ;
- pessimiste : 2 436 secondes, soit 40 min 36 s ;
- écart : 1 198 secondes, soit près du double.
Chiffres d'un exemple précis, pas une règle. Même trajet, même carte, deux hypothèses.
CE QUI EXPLOSE, C'EST LE NOMBRE DE CHEMINS, PAS LE CALCUL
Avec 3 choix à chaque intersection :
- 5 intersections : 3^5 = 243 ;
- 10 intersections : 3^10 = 59 049 ;
- 15 intersections : 3^15 = 14 348 907.
La liste des chemins grimpe comme une puissance. Le travail de l'algorithme grimpe à peu près comme la taille du réseau.
Tout l'écart entre « impossible » et « deux secondes » est là.
UNE IDÉE PUBLIÉE EN 1959
L'article d'Edsger Dijkstra fait trois pages.
Son principe : avancer depuis le point dont le meilleur coût connu est le plus faible.
Il suppose des coûts jamais négatifs. C'est le cas d'une durée : aucune rue ne te rend du temps.
Bien implémentée, la méthode travaille en un temps de l'ordre de (V + E) log V : V sommets, E arêtes.
ON FAIT ENCORE MIEUX QUE L'EAU QUI SE RÉPAND
Dijkstra explore dans toutes les directions, y compris à l'opposé de ta destination.
Les variantes employées en pratique ajoutent une estimation de la distance restante, pour regarder d'abord ce qui va dans le bon sens.
Le principe ne change pas : seul l'ordre d'exploration devient plus malin.
CE QUE FAIT VRAIMENT GOOGLE MAPS RESTE EN PARTIE INCONNU
Google documente ce que ses interfaces calculent, pas l'architecture interne de l'application.
Dire « Google Maps applique Dijkstra » serait commode, et faux.
LE PIÈGE : PRENDRE « OPTIMAL » POUR « MEILLEUR EN TOUT »
« C'est le chemin le plus court. » — En kilomètres ou en minutes ?
« C'est le meilleur trajet. » — Selon quel critère, avec quelles données ?
« Tu gagnes 5 minutes par là. » — Une estimation, pas une promesse.
« C'est optimisé. » — Optimisé pour qui ?
Un itinéraire est optimal pour le coût qu'on lui a donné, et pour rien d'autre. Ce coût, tu ne le choisis presque jamais : quelqu'un l'a fixé avant toi.
COMMENT MIEUX DÉCIDER
1. Nomme les lieux qui comptent : tes sommets.
2. Relie ceux qu'on atteint directement : tes arêtes.
3. Choisis un seul coût : minutes, francs, fatigue, risque.
4. Additionne-le le long de chaque option.
5. Compare avec le même critère.
6. Recalcule quand les conditions changent.
L'IDÉE À RETENIR
Trouver un itinéraire, ce n'est pas essayer toutes les routes.
C'est transformer le terrain en graphe, décider ce qu'on appelle « coût », puis explorer dans le bon ordre.
Le choix du coût précède le calcul, et c'est lui qui décide de la réponse.
RESSOURCES
1. Interstices (Inria) — « Le plus court chemin »
Le déroulé complet de Dijkstra, pseudo-code inclus.
2. VisuAlgo (National University of Singapore)
Dessine ton graphe, lance Dijkstra, regarde l'exploration avancer sommet par sommet. En anglais, mais l'animation parle d'elle-même.
3. Google Maps Platform — modèles de trafic
La source des chiffres du point
: une durée affichée résulte d'un modèle, pas d'une mesure.
