Comment un GPS trouve-t-il le plus court chemin sans essayer tous les itinéraires ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Quand j'utilise une application de navigation, elle trouve un itinéraire en une seconde, alors qu'il existe des milliards de chemins possibles entre deux villes. En NSI, j'ai découvert l'algorithme de Dijkstra, publié en 1959. J'ai voulu comprendre son principe, l'appliquer à la main sur un petit réseau, et surtout comprendre pourquoi on peut être sûr qu'il donne le chemin le plus court.

L'enjeu et les notions du programme

Modéliser un réseau routier par un graphe pondéré et justifier la correction d'un algorithme glouton par un raisonnement sur les inégalités.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   On représente un réseau routier par un graphe : les sommets sont des villes, les arêtes des routes, chacune pondérée par sa longueur. Problématique : comment trouver le plus court chemin entre deux villes sans énumérer tous les chemins ?

2. 2. NSI : l'algorithme pas à pas

   3,5 min

   Graphe : A–B 4, A–C 2, C–B 1, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 2. On cherche le chemin de A à F.

   On attribue à chaque sommet une distance provisoire (0 pour A, l'infini ailleurs). À chaque étape, on choisit le sommet non traité de plus petite distance, on le fixe, et on met à jour ses voisins si passer par lui est plus court.

   Étape 1 : A (0) ; B = 4, C = 2. Étape 2 : C (2) ; B devient 3 (via C), D = 10, E = 12. Étape 3 : B (3) ; D devient 8. Étape 4 : D (8) ; E devient 10, F = 14. Étape 5 : E (10) ; F devient 12. Étape 6 : F (12). En remontant les prédécesseurs : A → C → B → D → E → F, longueur 12.

3. 3. Mathématiques : pourquoi le résultat est juste

   3,5 min

   Propriété : quand un sommet est fixé, sa distance est la vraie plus courte distance depuis A. Raisonnons par l'absurde : supposons qu'au moment où l'on fixe $u$u avec la distance $d(u)$d(u), il existe un chemin plus court, de longueur $L<d(u)$L<d(u). Ce chemin part de A (fixé) et doit, à un moment, quitter l'ensemble des sommets fixés par un premier sommet non fixé $v$v.

   La distance provisoire de $v$v est au plus la longueur du début de ce chemin, elle-même au plus $L$L car les poids sont positifs. Donc $d(v)\le L<d(u)$d(v)≤ L<d(u) : l'algorithme aurait dû choisir $v$v avant $u$u. Contradiction.

   La positivité des poids est essentielle : avec un poids négatif, la fin du chemin pourrait raccourcir le trajet, et l'algorithme se tromperait. Coût : environ $(n+m)\log n$(n+m)log n opérations pour $n$n sommets et $m$m arêtes avec une file de priorité, contre un nombre exponentiel de chemins.

4. 4. Conclusion

   1,5 min

   Un GPS n'essaie pas tous les itinéraires : Dijkstra fixe les sommets dans l'ordre croissant de distance, et la positivité des poids garantit que chaque distance fixée est définitive. J'ouvre sur l'algorithme A*, qui accélère encore la recherche en estimant la distance restante à vol d'oiseau.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Fixer un sommet avant qu'il soit le plus proche.
• Oublier l'hypothèse de poids positifs.
• Confondre plus court chemin et circuit passant par toutes les villes.

Revoir les notions

• Graphes et marches aléatoires (Terminale maths expertes) →
• Algorithmique et Python (Terminale spé maths) →

Autres questions : graphes et réseaux

• Comment classer les pages du web par importance en ne regardant que les liens entre elles ?
• Peut-on parcourir tous les ponts d'une ville une seule fois chacun ? Le problème des ponts de Königsberg
• Est-il vrai que tout le monde sur Terre est relié à n'importe qui par une chaîne de six connaissances ?
• Combien de créneaux faut-il au minimum pour organiser des examens sans qu'aucun élève n'en ait deux en même temps ?

Toutes les questions maths-nsi →