Techniques et concepts de l'entreprise, de la finance et de l'économie 
(et fondements mathématiques)

L'algorithme de Dijkstra

logo

 

 

 

 

 

 

 

 

 

 

Graphes pondérés et algorithme de Dijkstra

Un graphe, orienté ou non orienté, est soit pondéré, 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é...

Divers algorithmes permettent de découvrir le chemin le plus court.

Aujourd’hui, les élèves de terminale ES spécialité maths connaissent tous celui qui fut proposé par Edsger Dijkstra, citoyen hollandais au nom imprononçable décédé en 2002.

Cet algorithme s’applique aussi bien aux graphes 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.

« 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. »

graphe pondéré

NB : il n’est pas obligatoire de passer par toutes les villes. Chaque ville 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 :

étape 1

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.

étape 2

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.

étape 3

À 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.

étape 4

À 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.

étape 5

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 avant de finalement rejoindre Berlin.

 

pirates et algorithme

 

© JY Baudot - Droits d'auteur protégés