Pour aller plus loin : l'algorithme de Dijkstra pour calculer un nombre de chemins
Mathématiques Expertes · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Définitions et théorèmes
L'algorithme de Dijkstra détermine, dans un graphe pondéré à poids positifs ou nuls, le plus court chemin (de poids total minimal) entre un sommet de départ et tous les autres sommets.
Principe par étiquetage :
Chaque sommet porte une étiquette égale à la plus courte distance connue depuis le départ. Initialement : 0 pour le départ, +\infty pour les autres.
On distingue les sommets provisoires (étiquette susceptible de baisser) et définitifs (fixés).
À chaque étape, on fixe le sommet provisoire d'étiquette minimale.
On met à jour (relâchement) les voisins du sommet fixé : si passer par lui raccourcit le chemin, on diminue leur étiquette et on note le prédécesseur.
L'algorithme s'arrête quand tous les sommets utiles sont fixés. On reconstruit le chemin en remontant les prédécesseurs depuis l'arrivée.
Formules
- Mise à jour : pour un voisin v du sommet fixé s,
\text{étiquette}(v)\leftarrow \min\big(\text{étiquette}(v),\ \text{étiquette}(s)+w(s,v)\big),
où w(s,v) est le poids de l'arête sv.
Méthodes type bac
Tableau d'étiquetage : dresser un tableau, une colonne par sommet, une ligne par étape ; à chaque étape repérer l'étiquette minimale, fixer le sommet, mettre à jour les voisins.
Suivre les prédécesseurs : noter à côté de chaque étiquette le sommet d'où elle provient.
Lire le résultat : l'étiquette définitive de l'arrivée est la distance minimale ; le chemin se lit en remontant les prédécesseurs.
Pièges
Dijkstra ne fonctionne avec garantie que pour des poids positifs ou nuls.
On fixe le sommet de plus petite étiquette provisoire, pas le premier rencontré.
Une étiquette ne peut que diminuer lors des mises à jour ; une fois un sommet fixé, son étiquette ne bouge plus.
Ne pas confondre la distance (somme des poids) avec le nombre d'arêtes du chemin.
Pour l'épreuve
Ce chapitre « pour aller plus loin » se traite essentiellement par un tableau d'étiquetage clair et ordonné. On attend la distance minimale, le chemin optimal (via les prédécesseurs) et l'ordre de fixation des sommets. La rigueur du tableau et la justification de chaque mise à jour sont valorisées. En pratique, on construit une colonne par sommet et une ligne par étape ; on barre une colonne dès que le sommet correspondant est fixé, et on reporte sur la ligne suivante les étiquettes mises à jour. Le chemin optimal se reconstitue ensuite en remontant les prédécesseurs depuis l'arrivée jusqu'au départ, ce qui fournit la liste ordonnée des sommets traversés. Cette présentation méthodique évite les erreurs et permet au correcteur de suivre chaque décision de l'algorithme.