Algorithme de Dijkstra - Définition

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

- Introduction - Principe sur un exemple - Principes - Notations - Codes - Algorithme - Applications

Algorithme

Fonction annexes

L'algorithme utilise les fonctions annexes suivantes.

Initialisation de l'algorithme

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

Recherche du nœud le plus proche

On recherche le nœud le plus proche (relié par l'arête de poids le plus faible) de $s d e b$ 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

On met à jour des distances entre $s d e b$ 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

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 d e b$ à $s f i n$ peut ensuite se calculer itérativement selon l'algorithme suivant, avec $A$ la suite représentant le plus court chemin de $s d e b$ à $s f i n$ :

      1 A = suite vide      2 s:= sfin      3 A = s + A                   /* insère s au début de A */      4 tant que s != sdeb      5   s = prédecesseur[s]       /* on continue de suivre le chemin */      6   A = s + A

Améliorations de l'algorithme

Il est possible d'améliorer légèrement l'algorithme principal en arrêtant la recherche lorsque l'égalité $s 1 = s f i n$ est vérifiée, à condition bien sûr de ne chercher que la distance minimale entre $s d e b$ et $s f i n$ .

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 : $\sigma [(m+n)\times ln(n)]$ . L'utilisation de tas de Fibonacci donne un meilleur temps d'exécution amorti : $\sigma [m+n\times ln(n)]$ .

Applications

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

Les routeurs IS-IS utilisent également l'algorithme. Les sites d'itinéraires routiers l'utilisent de la même manière et permettent de nombreuses adaptations en ajustant le poids des arcs comme par exemple : trajet le plus économique, le plus rapide...