Algorithme de Dijkstra
Exemple tiré de l'activité proposée par Alexandre Tartarin,
document d'accompagnement SNT, académie de Rouen
M. GEORGES-SAINT-MARC, A. MEUDEC – Lycée PMF Rennes, 2020
Edsger Dijkstra (1930 – 2002)
•Mathématicien et informaticien
néerlandais
•Débute dans l'informatique après
ses études de physique en 1955
• Connu principalement pour
l'algorithme portant son nom
•Recherches importantes allant
bien au delà de cet algorithme
•Reçoit notamment le prix Turing
en 1972
Edsger Dijkstra à l'ETH de Zurich en 1994
(Photo : Andreas F. Borchert, CC BY-SA 4.0)
2 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Algorithme de Dijkstra (1959)
→ Permet de déterminer le chemin le
plus court sur un graphe entre deux
sommets.
B 2 D
3 3
Rappels :
• Graphe : ensemble de sommets A 2 3 1 F
reliés par des arêtes
• Poids des arêtes : valeur 1 1
numérique associée à une arête. C E
→ Peut notamment représenter une 5
distance, un temps ou un coût de
déplacement entre deux endroits.
3 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Algorithme de Dijkstra (1959)
Problème à résoudre
Quel est le trajet le plus court entre les
→ Permet de déterminer le chemin le sommets A et F ?
plus court sur un graphe entre deux
sommets.
B 2 D
3 3
Rappels :
• Graphe : ensemble de sommets A 2 3 1 F
reliés par des arêtes
• Poids des arêtes : valeur 1 1
numérique associée à une arête. C E
→ Peut notamment représenter une 5
distance, un temps ou un coût de
déplacement entre deux endroits.
4 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Algorithme de Dijkstra (1959)
→ Exemple à traiter simple, mais
algorithme intéressant pour des
graphes plus complexes, comme :
5 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Fonctionnement de l'algorithme
Quel est le trajet le plus court entre les sommets A et F ?
∞ ∞
Initialisation : étiquette 2
B D
● On se place sur le sommet A, et on «
oublie » toutes les arêtes. 3 3
0 ∞
● Chaque sommet est étiqueté par la
A 2 3 1 F
distance la plus courte le reliant à A :
→ la distance entre A et A est 0.
1 1
→ la distance entre A et tout autre
sommet est infinie.
C E
5
∞ ∞
6 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Fonctionnement de l'algorithme
Quel est le trajet le plus court entre les sommets A et F ?
3 ∞
Premier sommet : A
B 2 D
● Les arêtes issues de A sont tracées.
3 3
● Les distances de A aux sommets B et C 0 ∞
sont désormais connues :
A 2 3 1 F
→ distance A – B : 3
→ distance A – C : 1 1 1
→ les autres distances ne changent C E
pas. 5
1 ∞
7 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Fonctionnement de l'algorithme
Quel est le trajet le plus court entre les sommets A et F ?
Sommet suivant : C
● On se place sur le sommet pas encore traité dont
l'étiquette est la plus faible valeur : C
3 4
●On considère les arêtes issues de C, et on actualise les 2
distances entre A et chacun des sommets : B D
3 3
→ chemin A-C-A : longueur 2. 0 ∞
C'est plus long que l’étiquette actuelle de A : 0 .
On ne change rien. A 2 3 1 F
→ chemin A-C-B : longueur 3.
C'est identique à l’étiquette de B : 3 .
On ne change rien. 1 1
→ chemin A-C-D : longueur 4.
C'est mieux que ∞ : on change la valeur. C E
→ chemin A-C-E : longueur 6.
5
C'est mieux que ∞ : on change la valeur. 1 6
● Les chemins les plus courts depuis A sont mémorisés
(arêtes en bleu).
8 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Fonctionnement de l'algorithme
Quel est le trajet le plus court entre les sommets A et F ?
Sommet suivant : B 3 4
B 2 D
B est le sommet non encore traité portant la plus petite
étiquette. On considère les arêtes issues de B, et on
3 3
actualise les distances entre A et chacun des sommets : 0 ∞
→ chemin A-B-A : longueur 3 + 3 = 6 > 0. Trop long A 2 3 1 F
→ chemin A-B-C : longueur 3 + 2 = 5 > 1. Trop long
1 1
→ chemin A-B-D : longueur 3 + 2 = 5 > 4. Trop long
C E
5
1 6
9 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Fonctionnement de l'algorithme
Quel est le trajet le plus court entre les sommets A et F ?
Sommet suivant : D
Même raisonnement que précédemment. Le plus court
chemin pour se rendre à D est A-C-D : longueur 4.
Partant de D : 3 4
B 2 D
→ chemin A-C-D-B : longueur 4 + 2 = 6 > 3. Trop long
3 3
→ chemin A-C-D-C : longueur 4 + 3 = 7 > 1. Trop long 0 7
→ chemin A-C-D-E : longueur 4 + 1 = 5 < 6 : mieux. A 2 3 1 F
→ chemin A-C-D-E : longueur 4 + 3 = 7.
1 1
C E
5
1 6 5
10 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Fonctionnement de l'algorithme
Quel est le trajet le plus court entre les sommets A et F ?
3 4
Sommet suivant : E
B 2 D
Même raisonnement que précédemment. Le plus court
chemin pour se rendre à E est A-C-D-E : longueur 5. 3 3
Partant de D : 0 7 6
A 2 3 1 F
→ chemin A-C-D-E-C : longueur 5 + 5 = 10 > 1. Trop long
→ chemin A-C-D-E-D : longueur 5 + 1 = 6 > 4. Trop long 1 1
→ chemin A-C-D-E-F : longueur 5 + 1 = 6 < 7 : mieux. C E
5
1 5
11 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Fonctionnement de l'algorithme
Quel est le trajet le plus court entre les sommets A et F ?
3 4
B 2 D
Sommet final : F 3 3
0 6
Tous les sommets menant à F ont été examinés. A 2 3 1 F
Le chemin le plus court est donc indiqué : il s'agit de
A–C–D–E-F
1 1
C E
5
1 5
12 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Applications
13 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Applications
14 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Applications
15 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Applications
16 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
Limites
L'algorithme de Dijkstra est efficace mais
nécessite de parcourir un grand nombre de
sommets du graphe avant de répondre au
problème donné.
→ Cela pose peu de problème dans les
exemples vus jusqu'ici.
→ Cela en pose plus pour des graphes
contenant des milliards de sommets et d'arêtes Comparatif Dijkstra / A*
(le réseau routier d'un pays, par exemple).
Pour cela, des améliorations ont été apportées
à l'algorithme de Dijkstra, en réduisant par
exemple les recherche dans un « rayon »
donné dans le graphe.
→ La plus célèbre amélioration s'appelle
l'algorithme A*.
17 Algorithme de Dijkstra - M. GEORGES-SAINT-MARC, A. MEUDEC (2020) Lycée PMF, Rennes
