Algorithme de Dijkstra

Correction du TD 23

Quel est le plus court chemin reliant A à H ?

• On construit un tableau avec le nom de tous les sommets, et on place 0 dans le sommet A et ∞ dans les autres

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

• On sélectionne le sommet qui a la plus faible valeur : A

• On barre la colonne du sommet selectionné : A

• On cherche les sommets adjacents à A : B, I et J

• On repère leur coefficient, que l’on va ajouter à la valeur du sommet précedemment selectionné : A (0)

4

8

5

4

8

5

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞

• On rempli le tableau en additionnant la valeur précédente avec le poids de l’arête considérée. Si la valeur est plus faible que celle inscrite dans la case au dessus, on la garde, sinon on conserve la précédente.

• On sélectionne le sommet de plus faible valeur : B

B

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞ B

5

6

4+59(B)

4+68(A) 5(A)∞ ∞ ∞ ∞ ∞ J

• pour le sommet I, la nouvelle valeur (10) est plus élevée que la précédente (8) donc on garde la plus faible

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞ B

4+59(B)

4+68(A) 5(A)∞ ∞ ∞ ∞ ∞ J

3

5+38(J)9(B) 8(A)∞ ∞ ∞ ∞

• Lorsque 2 sommets sont de même valeur, on peut choisir celui qu’on veut ! Optons par exemple pour G

G

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞ B

4+59(B)

4+68(A) 5(A)∞ ∞ ∞ ∞ ∞ J

5+38(J)9(B) 8(A)∞ ∞ ∞ ∞ G

5 2

8+58(A)

8+210(G)9(B) ∞ ∞ ∞ I

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞ B

4+59(B)

4+68(A) 5(A)∞ ∞ ∞ ∞ ∞ J

5+38(J)9(B) 8(A)∞ ∞ ∞ ∞ G

8+58(A)

8+210(G)9(B) ∞ ∞ ∞ I

4

8+49(B) 10(G)∞ ∞ ∞ C

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞ B

4+59(B)

4+68(A) 5(A)∞ ∞ ∞ ∞ ∞ J

5+38(J)9(B) 8(A)∞ ∞ ∞ ∞ G

8+58(A)

8+210(G)9(B) ∞ ∞ ∞ I

8+49(B) 10(G)∞ ∞ ∞ C

6

9+615(C) 10(G)∞ ∞ F

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞ B

4+59(B)

4+68(A) 5(A)∞ ∞ ∞ ∞ ∞ J

5+38(J)9(B) 8(A)∞ ∞ ∞ ∞ G

8+58(A)

8+210(G)9(B) ∞ ∞ ∞ I

8+49(B) 10(G)∞ ∞ ∞ C

9+615(C) 10(G)∞ ∞ F

3 2

10+313(F)

10+212(F)15(C) E

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞ B

4+59(B)

4+68(A) 5(A)∞ ∞ ∞ ∞ ∞ J

5+38(J)9(B) 8(A)∞ ∞ ∞ ∞ G

8+58(A)

8+210(G)9(B) ∞ ∞ ∞ I

8+49(B) 10(G)∞ ∞ ∞ C

9+615(C) 10(G)∞ ∞ F

10+313(F)

10+212(F)15(C) E

15(C) H

3

Une fois que le sommet d’arrivée a été sélectionné dans la dernière colonne : on s’arrête

12+313(F)

A B C D E F G H I J Sommet sélectionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A

0+44(A)

0+88(A)

0+55(A)∞ ∞ ∞ ∞ ∞ ∞ B

4+59(B)

4+68(A) 5(A)∞ ∞ ∞ ∞ ∞ J

5+38(J)9(B) 8(A)∞ ∞ ∞ ∞ G

8+58(A)

8+210(G)9(B) ∞ ∞ ∞ I

8+49(B) 10(G)∞ ∞ ∞ C

9+615(C) 10(G)∞ ∞ F

10+313(F)

10+212(F)15(C) E

12+315(E) 13(F) H

On lit le chemin à l’envers en allant vers la dernière case de la lettre entre parenthèse à partir du sommet H : H

13(F)

F -

10(G)

G -

5+38(J)

J -

5(A)

A - Avec un poids de 13

On vérifie : A-J-G-F-H avec un poids de 13

5 3 2

3

Facile !!!