Algorithme de Dijkstra

Edgser Wybe Dijkstra (1930-2002) a proposé en 1959 un algorithme qui permet de calculer le plus court chemin entre un sommet particulier et tous les autres. Le résultat est une arborescence.

Numérotons les sommets du graphe G = (V,E) de 1 à n. Supposons que l'on s'intéresse aux chemins partant du sommet 1.
On construit un vecteur l = (l(1); l(2); ...; l(n)) ayant n composantes tel que l(j) soit égal à la longueur du plus court chemin allant de 1 au sommet j. On initialise ce vecteur à c1,j, c'est-à-dire à la première ligne de la matrice des coûts du graphe, définie comme indiqué ci-dessous:

d(i,j) est le poids (la longueur) de l'arc (i,j). Les cij doivent être strictement positifs.
On construit un autre vecteur p pour mémoriser le chemin pour aller du sommet 1 au sommet voulu. La valeur p(i) donne le sommet qui précède i dans le chemin.
On considère ensuite deux ensembles de sommets, S initialisé à {1} et T initialisé à {2, 3, ..., n}. À chaque pas de l'algorithme, on ajoute à S un sommet jusqu'à ce que S = V de telle sorte que le vecteur l donne à chaque étape le coût minimal des chemins de 1 aux sommets de S.

Description de l'algorithme de Dijkstra

On suppose ici que le sommet de départ (qui sera la racine de l'arborescence) est le sommet 1. Notons qu'on peut toujours renuméroter les sommets pour que ce soit le cas.

Initialisations l(j) = c1,j et p(j) = NIL, pour 1 j n
Pour 2 j n faire
   Si c1,j < alors p(j) = 1.
S = {1} ; T = {2, 3, ..., n}.
Itérations Tant que T n'est pas vide faire
   Choisir i dans T tel que l(i) est minimum
   Retirer i de T et l'ajouter à S
   Pour chaque successeur j de i, avec j dans T, faire
      Si l(j) > l(i) + d(i,j) alors
            l(j) = l(i) + d(i,j)
            p(j) = i

Exemple
Initialisations S = {1} ; T = {2, 3, 4, 5} ; l = (0, 15, , , 4); p = (NIL, 1, NIL, NIL, 1)
Graphe de départ


Arborescence donnant les plus courts chemins du sommet 1 à tous les autres.
1ère itération i = 5 car l(5) = min(15, , , 4) = 4;
S = {1, 5}; T = {2, 3, 4};
les successeurs de 5 dans T sont 3 et 4;
l(3) prend la nouvelle valeur min(; l(5) + d(5; 3)) = min(; 4 + 7) = 11; p(3) = 5;
l(4) prend la nouvelle valeur min(; l(5) + d(5; 4)) = 9; p(4) = 5;
d'où les nouveaux vecteurs l = (0, 15, 11, 9, 4) et p = (NIL, 1, 5, 5, 1)
2e itération i = 4; l(4) = 9;
S = {1, 5, 4}; T = {2, 3};
le seul successeur de 4 dans T est 2;
l(2) prend la nouvelle valeur min(; l(4) + d(4; 2)) = min(15; 9 + 3) = 12; p(2) = 4;
d'où les nouveaux vecteurs l = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)
3e itération i = 3; l(3) = 11;
S = {1, 5, 4, 3}; T = {2};
le seul successeur de 3 dans T est 2;
l(2) garde sa valeur car min(12; l(3) + d(3; 2)) = min(12; 11 + 3) = 12;
d'où les vecteurs inchangés l = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)
4e itération i = 2; l(2) = 12;
S = {1, 5, 4, 3, 2}; T={}; FIN.
l = (0, 12, 11, 9, 4);
p = (NIL, 4, 5, 5, 1).

Le chemin minimal de 1 à 4 par exemple est de coût 9. C'est le chemin 1-5-4, car p(4) = 5 et p(5) = 1.


Exercices

Exercice 1

Appliquez l'algorithme de Dijkstra au graphe de l'exemple ci-dessus pour trouver tous les plus courts chemins en partant des sommets 2, 3, 4 et 5.
Vérifiez vos résultats avec l'applet prévue à cet effet.

Exercice 2

Expliquez pourquoi des arcs avec des poids négatifs pourraient poser problème dans la recherche d'un plus court chemin dans un graphe.

Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés!
Mot de passe :


Références


Didier Müller, 16.2.03