Algorithme de Dijkstra

E. W. Dijkstra (1930-2002) a proposé en 1959 un algorithme qui permet de déterminer le plus court chemin entre deux sommets d’un graphe connexe pondéré. L’algorithme est basé sur l’observation suivante : une fois que nous déterminons le chemin le plus court vers un sommet v, alors les chemins qui vont de v à chacun de ses sommets adjacents pourraient être le plus court chemin vers chacun de ces sommets voisins. L’algorithme de Dijkstra est un algorithme de programmation dynamique glouton, il visite toutes les solutions possibles.

Conditions

  • Pas de longueur négative
  • Arc ou arête
  • Nombre de sommets fini
  • Une source (et accessoirement une cible) définie

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 arêtes empruntées.

 

Sommet visité : Un sommet pour lequel nous avons déterminé le chemin le plus court. Une fois que nous avons défini un sommet comme VISITE, cela est définitif, et nous ne reviendrons plus sur ce sommet.
Sommet marqué : Un sommet pour lequel un chemin a été trouvé. Nous marquons ce sommet comme CANDIDAT pour le chemin le plus court.

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 (il devient un sommet visité). Ensuite, on met à jour les distances des sommets voisins de celui ajouté (les sommets sont marqués). 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’à compléter entièrement le sous-graphe (ou jusqu’à sélection du sommet d’arrivée). Exemple :

15e

 distance à 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)

Pour des raisons pratiques, la résolution de l’algorithme de Dijkstra ne retourne qu’un vecteur contenant le sommet visité, la liste des prédécesseurs (les sommets déjà validés) et les valeurs des plus courts chemins vers tous les autres sommets. Ce qui correspond à une ligne courante du tableau présenté. Grâce à la colonne de gauche, nous pouvons créer un arbre des chemins les plus courts du sommet A à tous les sommets.

dijkstra

Optimalité
Le sommet de départ est le chemin le plus court pour arriver à lui-même. Ensuite, nous calculons tous les chemins de taille 1 partant de ce sommet, afin d’en valider le plus court. Ce chemin est donc le plus court chemin à partir du sommet de départ car il n’y a pas d’arête de poids négatif. Par récurrence, nous en déduisons que l’algorithme valide toujours un plus court chemin.
d[0]=0, d[i]=infini pour tout sommet autre qu'origine
tant qu'il existe un sommet hors du sous-graphe 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
fin
retourner d
Publicités