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é.

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.

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’à 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é.

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