Problèmes de
cheminement
- Algorithme de Dijkstra-
Enseignante:
Olfa Layouni
E-mail:
1
Introduction (1)
o Les problèmes de cheminement sont des problèmes
classiques de la théorie des graphes.
o L'objectif est de calculer une route entre des sommets d'un
graphe qui minimise ou maximise une certaine fonction
économique.
2
Introduction (2)
o Le problème le plus classique consiste à chercher le chemin le plus
court entre deux sommets (qui minimise la somme des valuations des
arêtes traversées).
3
Introduction (3)
Problèmes de
cheminement
Plus
court
chemin
Bellman
Dijkstra
Floyd
Problème
d’ordon-
nancement
Voyageur
de
commerce
Postier
chinois
PERT
GANTT
Algorithmes
déterministes
Algorithmes
d’approximation
Graphes
Eulériens
minimaux
4
Problème du plus court
chemin
5
Définitions
◼ Le poids c(p) d’un chemin p est la somme des arrêtes le long du
chemin. Le poids d’un chemin est aussi appelé longueur du chemin.
◼ Étant donné un graphe valué et deux sommets u et v, nous voulons
trouver le chemin de poids total minimum entre u et v.
◼ Le plus court chemin entre 2 sommets u et v est alors défini comme le
chemin de plus faible poids reliant u et v.
➢ Dijkstra
6
Algorithme Dijkstra
Cet algorithme est une adaptation de l'algorithme de recherche
pour calculer les plus court chemin d'un sommet u à tous les
autres sommets du graphe.
7
Principe
o On construit petit à petit, à partir de {x0}, un ensemble M de
sommets marqués. Pour tout sommet marqués, l’estimation d(s) est
égale à la distance d(x0, s).
o A chaque étape, on sélectionne le sommet non marqué x dont la
distance estimée d(x) est la plus petite parmi tous les sommets non
marqués.
o On marque alors x (on rajoute x à M), puis on met à jour à partir de x
les distances estimées des successeurs non marqués de x.
Publicité
o On recommence, jusqu’à épuisement des sommets non marqués.
8
Algorithme Dijkstra
Initialisation
d(x0) = 0, P(x0) = nul
aucun sommet n’est marqué
min_dist_M = 0 (minimum des distances estimées des sommets non marqués)
pour tout s ∈ S, s x0 répéter
d(s) = +∞, P(s) = nul
répéter
chercher x non marqué tel que d(x) = min_dist_M
marquer x
pour tout y ∈ G(x), y non marqué répéter
si d(x) + v(x, y) < d(y) alors
d(y) ← d(x) + v(x, y) (màj distance)
P(y) ← x (màj père)
min_dist_M = min{d(s), s M}
Jusqu’à ce que M = S
9
A-B= 4
AC-CB
A-C=2
AC
A
8
2
B
2
C
d(A) d(B)
0
+∞
d(C)
+∞
P(A)
Nul
P(B)
P(C)
Nul
Nul
8
2+2=4
4<8
4
-
4
2
-
-
2
-
-
-
Nul
A
C
-
C
A
-
-
A
Choisir le minimum
10
M
{A}
{A, C}
{A, C, B}
-
-
-
{A,C,B}
Publicité
0
Exemple 1
8
B
A-C= 3, AD-DC
A-B=6, AD-DC-CB
A-D=2, AD
A
2
M
{A}
{A, D}
{A,D,C}
{A,D,C,
B}
{A,D,C,
B}
d(A
)
0
-
-
-
-
0
d(B) d(C) d(D) P(A) P(B
P(C) P(D)
)
+∞ +∞ +∞ Nul Nul Nul Nul
6
-
-
-
-
A
D
C
-
A
D
-
-
A
-
-
-
8
6
2
-
-
-
5+2
=7
3+3
=6
-
6
1+2
=3
-
-
3
5
D
1
3
C
2
Nul C
D
A
Publicité
11
Travail à faire
10
A
5
1
9
B
2
3
E
2
7
C
4
6
D
12
M
{A}
{A,E}
{A,E,D}
{A,E,D,
B}
{A,E,D,
B,C}
{A,E,D,
B,C}
-
-
-
-
-
0
d(A)
d(B)
d(C)
d(D)
d(E)
P(A)
0
+∞
+∞
+∞
+∞
Nul
10
+∞
+∞
5
3+5=
8
9+5=
14
2+5
=7
-
-
-
8
-
-
8
6+7=
13
1+8=
9
-
9
-
-
-
Publicité
-
-
-
-
-
-
7
5
Nul
E
Solution
P(D
)
Nul
P(E)
Nul
Nul
A
A
10
5
P(B
)
Nul
A
E
E
-
-
P(
C)
N
ul
N
ul
E
D
B
-
B
E
-
-
-
-
-
-
-
E
A
1
9
B
2
3
C
4
2
E
7
AB= 8
AE-EB
AC=9
AE-EB-BC
AD=7
AE-ED
AE=5
AE
6
D
13