Algorithme de Dijkstra

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Une exécution de l'algorithme

En théorie des graphes, l'algorithme de Dijkstra (prononcer [dɛj.kstra]) 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 routier d'une région. Il s'applique à un graphe connexe dont le poids lié aux arêtes est un réel positif.

L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra, et a été publié en 1959[1].

En théorie de la complexité, on démontre que cet algorithme est polynomial.

Principe sur un exemple[modifier | modifier le code]

Il s'agit de construire progressivement, à partir des données 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.

Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies. Au cours de chaque itération, on va mettre à jour les distances des sommets reliés par un arc au dernier du sous-graphe (en ajoutant le poids de l'arc à la distance séparant ce dernier sommet du sommet de départ ; si la distance obtenue ainsi est supérieure à celle qui précédait, la distance n'est cependant pas modifiée). Après cette mise à jour, on examine l'ensemble des sommets qui ne font pas partie du sous-graphe, et on choisit celui dont la distance est minimale pour l'ajouter au sous-graphe.

La première étape consiste à mettre de côté le sommet de départ et à lui attribuer une distance de 0. Les sommets qui lui sont adjacents sont mis à jour avec une valeur égale au poids de l'arc qui les relie au sommet de départ (ou à celui de poids le plus faible si plusieurs arcs les relient) et les autres sommets conservent leur distance infinie.

Le plus proche des sommets adjacents est alors ajouté au sous-graphe.

La seconde étape consiste à mettre à jour les distances des sommets adjacents à ce dernier. Encore une fois, on recherche alors le sommet doté de la distance la plus faible. Comme tous les sommets n'avaient plus une valeur infinie, il est donc possible que le sommet choisi ne soit pas un des derniers mis à jour.

On l'ajoute au sous-graphe, puis on continue ainsi à partir du dernier sommet ajouté, jusqu'à épuisement des sommets ou jusqu'à sélection du sommet d'arrivée.

Distance entre la ville A et la ville J[modifier | modifier le code]

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 sont alors 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 connaît ainsi le chemin le plus court menant de A à J, il passe par C et H et mesure 487 km.

Présentation sous forme de tableau[modifier | modifier le code]

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 Dijkstra 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 de départ, il est alors inutile de chercher d'autres distances de ce sommet au point 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.

Notations[modifier | modifier le code]

Le graphe est noté G=(S,A) où :

  • l'ensemble S est l'ensemble des sommets du graphe G ;
  • l'ensemble A est l'ensemble des arêtes de G tel que : si (s_1, s_2) est dans A, alors il existe une arête depuis le nœud s_1 vers le nœud s_2 ;
  • on définit la fonction Poids(s_1,s_2) définie sur A qui renvoie le poids positif de l'arête reliant s_1 à s_2 (et un poids infini pour les paires de sommets qui ne sont pas connectées par une arête).

Principe[modifier | modifier le code]

Dijkstra's algorithm.svg

Le poids du chemin entre deux sommets est la somme des poids des arêtes qui le composent. Pour une paire donnée de sommets s_{deb} (le sommet du départ) s_{fin} (sommet d'arrivée) appartenant à S, l'algorithme trouve le chemin depuis s_{deb} vers s_{fin} de moindre poids (autrement dit le chemin le plus léger ou encore le plus court).

L'algorithme fonctionne en construisant un sous-graphe P de manière à ce que la distance entre un sommet s de P depuis s_{deb} soit connue et soit un minimum dans G. Initialement P contient simplement le nœud s_{deb} isolé, et la distance de s_{deb} à lui-même vaut zéro. Des arcs sont ajoutés à P à chaque étape :

1. en identifiant toutes les arêtes a_i=(s_{i1},s_{i2}) dans P \times G tel que s_{i1} est dans P et s_{i2} est dans G ;
2. en choisissant l'arête a_j=(s_{j1},s_{j2}) dans P \times G qui donne la distance minimum depuis s_{deb} à s_{j2} en passant tous les chemins créés menant à ce nœud.

L'algorithme se termine soit quand P devient un arbre couvrant de G, soit quand tous les nœuds d'intérêt[2] sont dans P.

On peut donc écrire l'algorithme de la façon suivante :

Entrées : G=(S,E) un graphe avec une valuation positive v des arêtes, s_{deb} un sommet de S

Initialiser tous les sommets comme étant « non marqué ». Affecter la valeur + \infty à tous les labels L
L(s_{deb}) = 0
Tant Qu'il existe un sommet non marqué
    Choisir le sommet a non marqué de plus petit label L
    Marquer a
    Pour chaque sommet b non marqué voisin de a
       L(b) = \min( L(b), L(a) + v(a, b) )
    Fin Pour
Fin Tant Que

Algorithme[modifier | modifier le code]

Fonctions annexes[modifier | modifier le code]

L'algorithme utilise les fonctions annexes suivantes.

Initialisation de l'algorithme[modifier | modifier le code]

Initialisation(G,sdeb)
1 pour chaque point s de G
2    faire d[s] := infini             /* on initialise les sommets autres que sdeb à infini */[3]
3 d[sdeb] := 0                        /* sdeb étant le point le plus proche de sdeb */

Recherche du nœud le plus proche[modifier | modifier le code]

  • On recherche le nœud le plus proche (relié par l'arête de poids le plus faible) de s_{deb} parmi les nœuds situés dans un ensemble Q, constitué des nœuds éloigné d'une arête des éléments de P. On utilise pour cela la fonction Trouve_min(). Le nœud trouvé est alors effacé de l'ensemble Q et est alors retourné à la fonction principale comme résultat de la fonction.

Mise à jour des distances[modifier | modifier le code]

  • On met à jour les distances entre s_{deb} et s_{2} en se posant la question : vaut-il mieux passer par s_{1} ou pas ?
maj_distances(s1,s2)
1 si d[s2] > d[s1] + Poids(s1,s2)
2    alors d[s2] := d[s1] + Poids(s1,s2)

Fonction principale[modifier | modifier le code]

Voici la fonction principale utilisant les précédentes fonctions annexes :

Dijkstra(G,Poids,sdeb)
1 Initialisation(G,sdeb)
2 Q := ensemble de tous les nœuds
3 tant que Q n'est pas un ensemble vide
4       faire s1 := Trouve_min(Q)
5          Q := Q privé de s1
6          pour chaque nœud s2 voisin de s1
7              faire maj_distances(s1,s2)

Le plus court chemin de s_{deb} à s_{fin} peut ensuite se calculer itérativement selon l'algorithme suivant, avec A la suite représentant le plus court chemin de s_{deb} à s_{fin}:

1 A = suite vide
2 s := sfin
3 tant que s != sdeb
4   A = A + s                 /* on ajoute s à la suite A */
5   s = prédécesseur[s]       /* on continue de suivre le chemin */

Améliorations de l'algorithme[modifier | modifier le code]

Il est possible d'améliorer légèrement l'algorithme principal en arrêtant la recherche lorsque l'égalité s_1=s_{fin} est vérifiée, à condition bien sûr de ne chercher que la distance minimale entre s_{deb} et s_{fin}.

L'algorithme de Dijkstra pourra être mis en œuvre efficacement en stockant le graphe sous forme de listes d'adjacence et en utilisant un tas comme une file à priorités pour réaliser la fonction Trouve_min. Si le graphe possède m arcs et n nœuds, en supposant que les comparaisons des poids d'arcs soient à temps constant, et que le tas soit binomial, alors la complexité de l'algorithme est : O((m+n)\times ln(n)). L'utilisation de tas de Fibonacci donne un meilleur temps d'exécution amorti : O(m+n\times ln(n)).

Pseudo-code[modifier | modifier le code]

 Fonction Dijkstra (nœuds, fils, distance, début, fin)
     Pour n parcourant nœuds
         n.parcouru = infini   // Peut être implémenté avec -1 (*)
         n.précédent = 0
     Fin pour
     début.parcouru = 0
     pasEncoreVu = nœuds
     Tant que pasEncoreVu != liste vide
         n1 = minimum(pasEncoreVu)   // Le nœud dans pasEncoreVu avec parcouru le plus petit
         pasEncoreVu.enlever(n1)
         Pour n2 parcourant fils(n1)   // Les nœuds reliés à n1 par un arc
             Si n2.parcouru > n1.parcouru + distance(n1, n2)   // distance correspond au poids de l'arc reliant n1 et n2
                 n2.parcouru = n1.parcouru + distance(n1, n2)
                 n2.précédent = n1   // Dit que pour aller à n2, il faut passer par n1
             Fin si
         Fin pour
     Fin tant que
     chemin = liste vide
     n = fin
     Tant que n != début
         chemin.ajouterAvant(n)
         n = n.précédent
     Fin tant que
     chemin.ajouterAvant(début)
     Retourner chemin
 Fin fonction Dijkstra

(*) Dans ce cas, minimum deviendra minimumPositif et n2.parcouru > ... deviendra n2.parcouru < 0 Ou n2.parcouru > ...

Application[modifier | modifier le code]

L'algorithme de Dijkstra trouve son utilité dans le calcul des itinéraires routiers. Le poids des arcs pouvant être la distance (pour le trajet le plus court), le temps estimé (pour le trajet le plus rapide), la consommation de carburant et le prix des péages (pour le trajet le plus économique).

Une application des plus courantes de l'algorithme de Dijkstra est le protocole open shortest path first (OSPF) qui permet un routage internet très efficace des informations en cherchant le parcours le plus efficace.

Les routeurs IS-IS utilisent également cet algorithme.

Avantages et inconvénient[modifier | modifier le code]

L'algorithme de Dijkstra, très puissant, admet quand même quelques limites :

  • Il demande une certaine masse de traitements quand le graphe devient grand. Quand la puissance matérielle est limitée, ou que l'on souhaite traiter rapidement le problème du chemin le plus court, on peut utiliser d'autres algorithmes, tel A*, qui sont certes moins précis parfois, mais qui sont plus rapides et moins gourmands en ressources.
  • On ne peut pas affecter aux liaisons un poids négatif (boucle infinie dans le cas d'un cycle de poids négatif).

Cependant il a plusieurs avantages :

  • Contrairement à l'algorithme A* par exemple, il trouve toujours le chemin ayant le poids le plus faible.

Notes et références[modifier | modifier le code]

  1. (fr) Principes de l'algorithme de Dijkstra, site Nimbustier.net.
  2. Par exemple, les nœuds n'ayant pas d'arêtes autres que celle que l'on a parcourue pour arriver à eux, ne sont pas considérés comme des nœuds d'intérêt.
  3. La suite de caractères /* ... */ est un commentaire.

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]