L’algorithme de Dijkstra dans un graphe pondéré et orienté en plus de 128 mots

Pour un sommet source donné dans le graphique, l’algorithme recherche le chemin le plus court entre ce nœud et tous les autres.

Ici on utilise un graphe pondéré qui est un graphe dans lequel chaque arc (cas d’un graphe orienté) reçoit un poids. Un graphe pondéré est donc un type spécial de graphe étiqueté dans lequel les étiquettes sont des nombres.

Le poids d’une chaîne ou d’un chemin est la somme des poids des arcs qui constituent la chaine.

L’algorithme prend en entrée un graphe pondéré et un sommet à partir duquel il calcule les distances, les étapes sont les suivantes :

Phase d’initialisation :

  • On positionne sur tous les sommets une étiquette égale à l’infini (ou a la longueur maximum possible +1).
  • On initialise l’étiquette sur A à 0

Phase de traitement :

  • On traite un sommet (ici on commence par A)
  • On marque le sommet comme visité
  • On relâche les arcs sortants du sommet, c’est à dire on cherche à mettre à jour la valeur de l’étiquette du sommet d’arrivée selon la distance.
  • Si la valeur de la route vers le sommet d’arrivée est inférieure à celle calculée, on met à jour l’étiquette du sommet avec cette distance totale.
  • Le sommet suivant à traiter est celui qui porte le poids le plus faible.

Exemple :

Initialisation de l’algorithme
On relâche l’arc sortant A-B, la distance est 15, 15 étant une meilleure valeur que l’infini on met à jour l’étiquette de B avec 15
On relâche l’arc sortant A-C la distance 4 étant meilleure que l’infini on met à jour l’étiquette du sommet C
Le sommet suivant de l’algorithme est celui qui n’est pas encore visité et qui a l’étiquette avec la plus faible valeur. Ici il s’agit du sommet C avec la valeur 4.
On relâche l’arc sortant C-E, la distance calculée depuis le sommet A est 4 + 11 = 15. 15 étant meilleure que l’infini on met à jour l’étiquette du sommet E.
On relâche l’arc sortant C-D, la distance calculée depuis le sommet A est 4 + 2 = 6. 6 étant meilleure que l’infini on met à jour l’étiquette du sommet D.

A l’étape suivante on visite le sommet D car sa valeur est la plus faible du graphe
On relâche l’arc sortant D-E et on calcule la distance depuis le sommet A qui est égale à 9 soit une distance plus courte que 15 (calculé à l’étape précédente)
On désélectionne alors l’arc C-E qui était auparavant calculé comme la meilleure route pour aller de A à E et on met à jour le sommet E avec la valeur 9.
Le sommet E est ensuité traité, il n’a pas d’arc sortant donc il n’y a pas de mise à jour.
Le sommet B est traité : l’arc sortant B-E est relâché, la distance de 15 + 5 = 20 étant supérieure à la valeur de 9 du sommet E il n’y a aucune mise à jour et l’algorithme se termine.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *