Chapitre 4 III - Algorithme de Dijkstra

Graphes pondérés
L’algorithme de Dijkstra permet de déterminer le plus court chemin entre deux
sommets. On construit de proche en proche le chemin cherché en choisissant
I - Graphe étiqueté un sommet du graphe parmi ceux qui n’ont pas encore été traités, tel que la
longueur connue provisoirement, étape après étape, soit la plus courte possible.

Un graphe étiqueté est un graphe dont les arêtes sont affectées d’étiquettes. Ces — Étape 1 : Affecter le poids 0 au sommet d’origine, et, provisoirement un
D ÉF.

étiquettes peuvent être des nombres, des lettres, des mots ou des symboles. poids ∞ aux autres sommets.
— Puis, répéter les opérations suivantes tant que le sommet de sortie n’est

D ÉF.
pas affecté d’un poids définitif :
— Étape 2 : Parmi les sommets dont le poids n’est pas définitivement
fixé, fixer le sommet de poids minimal.
E XEMPLE ( S ) d
a
b
e — Étape 3 : Pour tous les sommets qui ne sont pas définitivement fixés,
Dbut . . Fin adjacents au dernier sommet fixé : ajouter le poids de l’arête au poids
c du sommet fixé. Si cette somme est inférieure au poids provisoire, on
affecte à ce sommet cette somme et on précise le sommet d’où provient
ce plus court chemin.

E XEMPLE ( S )
II - Graphe pondéré Nous allons déterminer le plus court chemin allant de A à F.
3 3
A B D
Un graphe pondéré est un graphe étiqueté dont les arêtes sont affectées de
nombres positifs (appelés poids). 1 3 3
1 1
Le poids d’une chaîne est la somme des poids des arêtes constituant cette
D ÉF.

chaîne. 5 1
La plus courte chaîne entre deux sommets donnés est la chaîne de poids mini- C E F
mal parmi toutes les chaînes reliant ces deux sommets. A B C D E F Sommet fixé Chemin le plus

✬ ✩0
court
A TON TOUR ! #1 ∞ ∞ ∞ ∞ ∞ A(0) (A-A) = 0
Donner la plus courte chaîne entre les sommets A et C. / 3(A) 1(A) ∞ ∞ ∞ C(1) prove- (A-C) = 1
B
nant de A
3 4 / 2(C) / 4(C) 6(C) ∞ B (2) prove- (A-C-B) = 2
nant de C
6 / / / 5(B)
✟
✟ 4(C)
✟ 6(C) ∞ D(4) prove- (A-C-D) = 4
A C
nant de C
2 / / / / 5(D) 7(D) E(5) prove- (A-C-D-E) = 5
2 nant de D
/ / / / / 6(E) F(6) prove- A-C-D-E-F = 6
✫ ✪
E D nant de E
1

C HAPITRE 4- G RAPHES PONDÉRÉS