Problèmes de cheminement - Algorithme de Dijkstra-
Enseignante: Olfa Layouni E-mail: [email protected]
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.
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
Publicité
-
-
2
-
-
-
Nul
A
C
-
C
A
-
-
A
Choisir le minimum
10
M
{A}
{A, C}
{A, C, B}
-
-
-
{A,C,B}
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
-
-
Publicité
-
5+2 =7
3+3 =6
-
6
1+2 =3
-
-
3
5
D
1
3
C
2
Nul C
D
A
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
Publicité
-
-
8
6+7= 13
1+8= 9
-
9
-
-
-
-
-
-
-
-
-
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