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 un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre une source et un sommet d'arrivée.

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

Cet algorithme est de complexité polynomiale.

Principe sur un exemple[modifier | modifier le code]

L'algorithme prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source. Il s'agit de construire progressivement 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 arcs empruntées.

Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies sauf pour le sommet de départ pour lequel la distance est de 0. Le sous-graphe de départ est l'ensemble vide.

Au cours de chaque itération, on choisit en dehors du sous-graphe un sommet de distance minimale et on l'ajoute au sous-graphe. Ensuite, on met à jour les distances des sommets voisins de celui ajouté. La mise à jour s'opère comme suit : la nouvelle distance du sommet voisin est le minimum entre la distance existante et celle obtenue en ajoutant le poids de l'arc entre sommet voisin et sommet ajouté à la distance du sommet ajouté.

On continue ainsi 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'algorithme de Dijkstra fonctionne aussi sur un graphe non orienté (qui peut le plus peut le moins). 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 : on choisit la ville A. On met à jour les villes voisines de A qui sont B, C, et E. Leurs distances deviennent respectivement 85, 217, 173, tandis que les autres villes restent à une distance infinie.
Étape 2 : on choisit la ville B. En effet, c'est la ville hors du sous-graphe qui est à la distance minimale (85). On met à jour le seul voisin (F). Sa distance devient 85+80 = 165.
Étape 3 : on choisit F. On met à jour le voisin I (415).
Étape 4 : on choisit E. On met à jour le voisin J (675).
Étape 5 : la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville C. On choisit donc C. On met à jour la ville G (403) et la ville H (320).
Étape 6 : la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville H (320). On choisit donc H. On met à jour la ville D (503) et la ville J (487< 675).
Étape 7 : la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance.
Étape 8 : la distance la plus courte suivante est celle de la ville I. La distance de la ville voisine J n'est pas modifiée car la distance existante est inférieure à celle que l'on obtiendrait en passant par I (415 + 84 > 487).
Étape 9 : la ville dont la distance est la plus courte est J (487). On choisit J et on l'ajoute au sous-graphe. On s'arrête puisque la ville d'arrivée est maintenant dans le sous-graphe.

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]

On peut aussi résumer l'exécution de l'algorithme de Dijkstra avec un tableau. Chaque étape correspond à une ligne. Une ligne donne les distances courantes des sommets depuis le sommet de départ. Une colonne donne l'évolution des distances d'un sommet donné depuis le sommet de départ au cours de l'algorithme. La distance d'un sommet choisi (car minimale) est soulignée. Les distances mises à jour sont barrées si elles sont supérieures à des distances déjà calculées.

Algorithme de Dijkstra
à A à B à C à D à E à F à G à H à I à J
étape initiale 0
A(0) 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 675487
G(403C) - - 503 - - - - 415 487
I(415F) - - 503 - - - - - 487
J(487H) - - 503 - - - - - -
D(503H) - - - - - - - - -

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

Schéma d'algorithme[modifier | modifier le code]

Dijkstra's algorithm.svg

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

  • l'ensemble S est l'ensemble fini des sommets du graphe G ;
  • l'ensemble A est l'ensemble des arcs de G tel que : si (s_1, s_2) est dans A, alors il existe une arc depuis le nœud s_1 vers le nœud s_2 ;
  • on définit la fonction poids définie sur S \times S dans \mathbb{R}^+ qui à un couple (s_1, s_2) associe le poids positif poids(s_1,s_2) de l'arc reliant s_1 à s_2 (et +\infty si s'il n'y a pas d'arc reliant s_1 à s_2).

Le poids du chemin entre deux sommets est la somme des poids des arcs 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 un chemin depuis s_{deb} vers s_{fin} de moindre poids (autrement dit un 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 arcs 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'arc 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,A) un graphe avec une valuation positive v des arcs, s_{deb} un sommet de S

P := \emptyset
d[a] := + \infty pour chaque sommet a
d(s_{deb}) = 0
Tant qu'il existe un sommet hors de P
    Choisir un sommet a hors de P de plus petite distance d[a]
    Mettre a dans P 
    Pour chaque sommet b hors de  P voisin de a
       d[b] = \min( d[b], d[a] + poids(a, b) )
    Fin Pour
Fin Tant Que

Implémentation de l'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 d'un nœud de distance minimale[modifier | modifier le code]

  • On recherche d'un nœud de distance minimale (relié par l'arc de poids le plus faible) de s_{deb} parmi les nœuds situés hors de P. Le complémentaire de P est noté Q. On implémente pour cela une fonction Trouve_min(Q) qui choisit un noeuds de Q de distance minimale.

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 */

Spécialisation de l'algorithme[modifier | modifier le code]

Il est possible de spécialiser l'algorithme en arrêtant la recherche lorsque l'égalité s_1=s_{fin} est vérifiée, dans lequel où on ne cherche que la distance minimale entre s_{deb} et s_{fin}.

Complexité de l'algorithme[modifier | modifier le code]

L'efficacité de l'algorithme de Dijkstra repose sur une mise en œuvre efficace de Trouve_min. On considère l'ensemble Q comme une file à priorités. Si le graphe possède |A| arcs et |S| nœuds, que le graphe est représenté par des listes d'adjacence, alors la complexité en temps de l'algorithme est O((|S|+|A|)\times\ln(|S|)) si on implémente la file à priorités par un tas binaire (en supposant que les comparaisons des poids d'arcs soient à temps constant). Si on implémente la file à priorités avec un tas de Fibonacci, l'algorithme est en O(|S|+|A|\times\ln(|S|))[4].

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

La démonstration de correction repose sur l'invariant suivant : les distances des sommets dans P sont les distances minimales[4]. L'algorithme de Dijkstra est un algorithme glouton.  

Applications[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). [réf. nécessaire]

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.[réf. nécessaire]

Les routeurs IS-IS utilisent également cet algorithme.

Comparaison avec d'autres algorithmes[modifier | modifier le code]

  • L'algorithme de DIjkstra est une spécialisation du parcours en largeur.
  • La spécialisation de l'algorithme de Dijkstra qui calcule un plus court chemin d'une source à une destination est une instance de l'algorithme A* dans lequel la fonction heuristique est la fonction nulle. L'algorithme A* qui utiliserait une heuristique minorante et monotone (par exemple la distance à vol d'oiseau) peut être plus efficace [réf. nécessaire].
  • L'algorithme ne s'applique pas aux graphes avec des poids négatifs. Mais l'algorithme de Bellman-Ford permet de résoudre le problème des plus courts chemins depuis une source avec des poids négatifs (mais sans cycle négatif).
  • L'algorithme de Floyd-Warshall calcule des plus courts chemins entre tous les sommets dans un graphe où les poids peuvent être négatifs.

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.
  4. a et b Cormen et al. 2010, p. 610

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]