Algorithme de Dijkstra - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction


En théorie des graphes, l'algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d'une ville à une autre connaissant le réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des...) routier d'une région. Il s'applique à un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) connexe dont le poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la...) lié aux arêtes est positif ou nul.

L'algorithme porte le nom de son inventeur, l'informaticien (On nommait dans les années 1960-1980 informaticien ou informaticienne une personne...) néerlandais Edsger Dijkstra (Edsger Wybe Dijkstra (né à Rotterdam le 11 mai 1930, mort à Nuenen le 6 août 2002) est un...) et a été publié en 1959.

En théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en...) on démontre que cet algorithme est polynomial.

Principe sur un exemple

Il s'agit de construire progressivement, à partir des données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent...) initiales, un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arêtes empruntées.

La première étape consiste à mettre de côté le sommet de départ et à repérer la distance du sommet de départ aux autres sommets du graphe. Cette distance est infinie si aucun arc ne relie le sommet au sommet de départ, elle est de n s'il existe un arc reliant ce sommet au sommet de départ et que le poids le plus faible (s'il existe plusieurs arcs) est de n.

La seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui...) étape consiste à repérer le sommet qui possède alors la plus courte distance au sommet de départ et à le mettre de côté. Pour tous les sommets restants, on compare alors la distance trouvée précédemment à celle que l'on obtiendrait via le sommet que l'on vient de mettre de côté et on ne conserve que la plus petite des valeurs. et on continue ainsi jusqu'à épuisement des sommets ou jusqu'à sélection du sommet d'arrivée.

Distance entre la ville (Une ville est une unité urbaine (un « établissement humain » pour...) A et la ville J

L'exemple suivant montre les étapes successives dans la résolution du chemin le plus court dans un graphe. Les nœuds symbolisent des villes identifiées par une lettre et les arêtes indiquent la distance entre ces villes. On cherche à déterminer le plus court trajet pour aller de la ville A à la ville J.

Étape 1 : à partir de la ville A, 3 villes sont accessibles, B, C, et E qui se voient donc affectées des poids respectifs de 85, 217, 173, tandis que les autres villes sont affectées d'une distance infinie.
Étape 2 : la distance la plus courte est celle menant à la ville B. Le passage par la ville B ouvre la voie à la ville F (85+80 = 165).
Étape 3 : La distance la plus courte suivante est celle menant à la ville F. Le passage par la ville F ouvre une voie vers la ville I (415).
Étape 4 : La distance la plus courte suivante est alors celle menant à la ville E. Le passage par la ville E ouvre une voie vers la ville J (675).
Étape 5 : la distance la plus courte suivante mène alors à la ville C. Le passage par la ville C ouvre une voie vers la ville G (403) et la ville H (320).
Étape 6: la distance la plus courte suivante mène à ville H(320). Le passage par la ville H ouvre une voie vers la ville D et un raccourci vers la ville J (487< 675).
Étape 7 : la distance la plus courte suivante mène à la ville G et ne change aucune autre distance.
Étape 8 : la distance la plus courte suivante mène à la ville I. Le passage par la ville I ouvre un chemin vers la ville J qui n'est pas intéressant (415+ 84 > 487).
Étape 9 : la distance la plus courte suivante mène à la ville J (487).

On connait ainsi le chemin le plus court menant de A à J, il passe par C et H et mesure 487 km.

De nos jours (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la...), l'algorithme de Dijkstra (En théorie des graphes, l'algorithme de Dijkstra sert à résoudre le problème du...) est utilisé dans plusieurs applications informatiques telles que les GPS. En outre, Google (Google, Inc. est une société fondée le 7 septembre 1998 dans la Silicon Valley en Californie par...) par exemple a pu introduire cet algorithme pour améliorer plusieurs fonctionnalités sur Google Maps (Google Maps est un service gratuit de carte géographique et de plan en ligne. Le service a...) ainsi que Google Earth (Google Earth est un logiciel, propriété de la société Google, permettant une...)..

Présentation sous forme de tableau (Tableau peut avoir plusieurs sens suivant le contexte employé :)

L'illustration par une série de graphes peut se révéler un peu longue. Il est d'autre part un peu plus difficile de repérer le chemin le plus court à l'issue du dessin. Ainsi l'algorithme de Dijsktra est souvent réalisé à l'aide d'un tableau dans lequel chaque étape correspond à une ligne.

À partir de la matrice des arcs orientés reliant les diverses villes :

Matrices des arcs orientés
à A à B à C à D à E à F à G à H à I à J
De A 0 85 217 173
De B 85 0 80
De C 217 0 186 103
De D 0 183
De E 173 0 502
De F 80 0 250
De G 186 0
De H 103 183 0 167
De I 250 0 84
De J 502 167 84 0

On construit un tableau dans lequel les distances d'un sommet au sommet de départ sont regroupées dans une même colonne. Les sommets sélectionnés sont soulignés. Les distances des voies ouvertes par la sélection d'un nouveau sommet sont barrées si elles sont supérieures à des distances déjà calculées. Quand un sommet est sélectionné, c'est que l'on a découvert sa distance minimale au sommet, il est alors inutile de chercher d'autres distances de ce sommet au point (Graphie) de départ.

Algorithme de Dijkstra
à B à C à D à E à F à G à H à I à J
A 85 217 173
B(85A) - 217 173 165
F(165B) - 217 173 - 415
E(173A) - 217 - - 415 675
C(217A) - - - - 403 320 415 675
H(320C) - - 503 - - 403 - 415 487
G(403C) - - 503 - - - - 415 487
I(415F) - - 503 - - - - - 499487
J(487H) - - 503 - - - - - -
D(503H) - - - - - - - - -

La construction de ce tableau donne non seulement la distance minimale de la ville A à la ville J mais aussi le chemin à suivre (J - H - C - A) ainsi que toutes les distances minimales de la ville A aux autres villes rangées par ordre croissant.

Page générée en 0.065 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique