Formation I.S.N.

Algorithme de Dijkstra

Chemin de poids minimum

Certains problèmes consistent à chercher entre deux points donnés le parcours qui a une "longueur" (durée, coût, distance) minimum.

Ces problèmes se ramènent à la recherche d'une chaîne ou d'un chemin de plus faible pondération entre deux sommets d'un graphe pondéré (les pondérations des arêtes étant toutes positives). On parlera de plus courte distance en interprétant les pondérations comme des distances entre les sommets.

L'algorithme de Dijkstra permet de résoudre ce type de problème dans les graphes pondérés connexes et à podérations positives.

L'algorithme de Dijkstra

Entrées

Un graphe pondéré connexe G (les poids sont tous positifs)

Un sommet d'entrée E
Résultat Les plus courtes distances du sommet E à chacun des sommets.
Traitement

Attribuer la marque \( +\infty \) à tous les sommets.

Attribuer la marque 0 au sommet d'entrée E.

TANT QU' il reste des sommets non sélectionnés :

  • Sélectionner, parmi les sommets non-sélectionnés, le sommet A ayant la marque la plus petite.
  • Pour chaque sommet B adjacent à A et non déjà sélectionné:
    • Calculer p = (marque de A) + (poids de l'arête A-B).
    • SI p < marque de B
      ALORS remplacer marque de B par p
      SINON conserver marque de B.

    • FIN TANT QUE

Remarques:

  1. Au premier tour de boucle, c'est le sommet E qui est sélectionné (puisqu'il porte la marque 0 et les autres la marque \(+\infty\)).
  2. Si l'objectif est de calculer la distance du sommet E à un sommet S, on peut stopper l'algorithme dès que S est parmi les sélectionnés.
  3. Si on veut connaître le chemin à suivre pour la plus courte distance, on ajoute à chaque étape une mémorisation du "parent" d'un sommet, ce qui donne:
    Entrées

    Un graphe pondéré connexe G (les poids sont tous positifs)

    Un sommet d'entrée E
    Résultat Les plus courtes distances du sommet E à chacun des sommets.
    Traitement

    Attribuer la marque \( +\infty \) à tous les sommets.

    Attribuer la marque 0 au sommet d'entrée E.

    père(E) = /

    TANT QU' il reste des sommets non sélectionnés :

    • Sélectionner, parmi les sommets non-sélectionnés, le sommet A ayant la marque la plus petite.
    • Pour chaque sommet B adjacent à A et non déjà sélectionné:
      • Calculer p = (marque de A) + (poids de l'arête A-B).
      • SI p < marque de B
        ALORS remplacer marque de B par p; père(B) = A
        SINON /

      • FIN TANT QUE

Un exemple "à la main"

Voici un graphe pondéré connexe. On cherche le plus court chemin emmenant du sommet E au sommet S.

E
E
A
A
B
B
C
C
D
D
S
S
3
3
2
2
3
3
4
4
3
3
2
2
5
5
2
2
2
2
2
2

Initialisation:

E (0)
E (0)
A (∞)
A (∞)
B (∞)
B (∞)
C (∞)
C (∞)
D (∞)
D (∞)
S (∞)
S (∞)
3
3
2
2
3
3
4
4
3
3
2
2
5
5
2
2
2
2
2
2

On sélectionne E et on actualise la marque de ses voisins:

E (0)
E (0)
A (3)
A (3)
B (2)
B (2)
C (∞)
C (∞)
D (∞)
D (∞)
S (∞)
S (∞)
3
3
2
2
3
3
4
4
3
3
2
2
5
5
2
2
2
2
2
2

Parmi les non sélectionnés, on sélectionne la marque la plus petite et on traite ses voisins non sélectionnés.

La marque du sommet A est inchangée puisque marque(B)+poids(B-A) > marque(A).

E (0)
E (0)
A (3)
A (3)
B (2)
B (2)
C (7)
C (7)
D (6)
D (6)
S(∞)
S(∞)
3
3
2
2
3
3
4
4
3
3
2
2
5
5
2
2
2
2
2
2

Parmi les non sélectionnés, on sélectionne la marque la plus petite et on traite ses voisins non sélectionnés.

La marque de C est modifiée puisque marque(A)+poids(A-C) < marque(C). Idem pour la marque de D. On modifie donc la couleur des arêtes (qui sert ici à enregistrer le "père").

E (0)
E (0)
A (3)
A (3)
B (2)
B (2)
C (6)
C (6)
D (5)
D (5)
S (∞)
S (∞)
3
3
2
2
3
3
4
4
3
3
2
2
5
5
2
2
2
2
2
2

Etape suivante:

E (0)
E (0)
A (3)
A (3)
B (2)
B (2)
C (6)
C (6)
D (5)
D (5)
S (7)
S (7)
3
3
2
2
3
3
4
4
3
3
2
2
5
5
2
2
2
2
2
2

Etape suivante:

E (0)
E (0)
A (3)
A (3)
B (2)
B (2)
C (6)
C (6)
D (5)
D (5)
S (7)
S (7)
3
3
2
2
3
3
4
4
3
3
2
2
5
5
2
2
2
2
2
2

Dernière étape:

E (0)
E (0)
A (3)
A (3)
B (2)
B (2)
C (6)
C (6)
D (5)
D (5)
S (7)
S (7)
3
3
2
2
3
3
4
4
3
3
2
2
5
5
2
2
2
2
2
2

Interprétation: la longueur minimale de E à S est 7 et en remontant les flèches violettes, on sait que le chemin correspondant est E-A-D-S.

On peut présenter la mise en oeuvre de l'algorithme de Moore-Dijkstra de la manière suivante (chaque ligne correspond à une étape de l'algorithme):

Tableau Moore-Dijkstra

Pour déterminer le résultat, on lit la chaîne à l'envers (en partant du sommet S) en se rendant dans la colonne du sommet de provenance.

Ainsi, la chaîne à l'envers est :

  • S (poids total = 7 en venant de D)
  • D (poids = 5 en venant de A)
  • A (poids = 3 en venant de E)
  • E (sommet d'entrée)

La chaîne de poids minimal est donc E-A-D-S