Graphes pondérés et algorithme de Dijkstra
Un graphe, orienté ou non orienté, est soit pondéré (ou valué), soit non pondéré. Lorsqu’il l’est, toutes les arêtes ne se valent pas puisqu’elles sont affectées de poids. L’enjeu est alors de rejoindre deux sommets avec un poids total minimum, plus rarement maximum. Cette pondération peut représenter une distance (kilomètres), une période, une probabilité... D'ailleurs c'est sur ce principe que fonctionnent les assistants d'aide à la conduite de type GPS.
Divers algorithmes permettent de découvrir le chemin le plus court.
Algorithme de Dijkstra
Jusqu'en 2020, les élèves de terminale ES spé maths connaissaient tous l'algorithme découvert par Edsger Dijkstra, citoyen hollandais au nom imprononçable décédé en 2002. Ce grand mathématicien et informaticien, qui n'utilisait jamais d'ordinateur pour écrire, a également révolutionné la façon dont sont construits les programmes et c'est un peu grâce à lui si aujourd'hui nous employons des conditions et des boucles...
Aujourd'hui, c'est dès la classe de seconde que l'on s'entraîne sur des itinéraires, non pas en cours de maths mais de SNT (Sciences numériques et technologie)
L'algorithme dit de Dijsktra s’applique aussi bien aux graphes non orientés qu'orientés. Il est en revanche inopérant si des pondérations sont négatives.
Un exemple servira de fil conducteur pour en expliquer le mécanisme. Il est extrait du sujet de baccalauréat d'Amérique du sud de novembre 2006.
Exemple
- Les lettres B, D, F, H, K, M, N et S représentent les villes Berlin, Dortmund, Francfort, Hambourg, Kaiserslautern, Munich, Nuremberg et Stuttgart. (…) Déterminer le plus court chemin possible pour aller de Kaiserslautern à Berlin.
Note : il n’est pas obligatoire de passer par toutes les villes. Chacune est représentée par un « sommet » du graphe.
Le poids 0 est affecté au premier sommet, c’est-à-dire à K. Le seul sommet qui lui est ADJACENT, F, est pondéré de 120 et les autres sommets reçoivent la valeur infinie. Le tableau qui nous guidera le long de l’exercice débute ainsi :
Précisons que s'il s'agissait d'un graphe orienté, il suffirait de chercher les sommets suivants au lieu des adjacents.
On fixe F (pas le choix puisqu’il est seul) par exemple en le colorant en rouge, puis H (pas le choix non plus). On indique les distances cumulées et le sommet prédécesseur (mais la présentation du tableau peut différer selon les auteurs). Trois nouveaux sommets sont adjacents à H.
On fixe N puisque ce sommet est le plus proche de H. Attention, ce n’est pas parce qu’un sommet est fixé qu’il sera utilisé. D’ailleurs, N ne nous servira pas. C'est juste un détour inutile entre H et S.
À présent, la chaîne la plus courte aboutit à S et c’est donc ce sommet qui est fixé. S est lié à B mais pas à D.
À présent, la plus courte chaîne mesure 1 390 km. On fixe M, ce qui permet de déterminer la distance entre K et D. Et ainsi de suite.
Pour connaître le plus court chemin, on relève que le sommet d’arrivée, c’est-à-dire B, a pour prédécesseur S, lequel vient après H, etc. Donc, le plus court trajet s’établit à 1 890 km. Départ de Kaiserslautern, puis une première étape à l’ombre des gratte-ciels de Francfort, une deuxième halte sur le port de Hambourg et une très inattendue descente à Stuttgart (illustration ci-dessous) avant de finalement rejoindre Berlin.
Voir un autre exemple en page d'exercice sur graphe non orienté.
