Chapitre 23
Problèmes de cheminement
1
Plan
Problème du plus court chemin
Algorithme Dijkstra
Algorithme Bellman-Ford
2
Introduction (1)
oLes 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.
3
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).
o Le problème de planification consiste à chercher le chemin le plus
court dans un graphe (chemin critique pour la réalisation d’un projet).
4
Problème du plus court
chemin
5
Problème du plus court chemin
(1)
Problèmes de
cheminement
Plus Problème Voyageur Postier
court d’ordon- de chinois
chemin nancement commerce
Algorithmes
Bellman-Ford Graphes
PERT déterministes
Dijkstra Eulériens
GANTT Algorithmes
Floyd minimaux
d’approximation
6
Problème du plus court chemin
(2)
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
➢ Bellman-Ford
➢ Floyd 7
Algorithme Dijkstra
8
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.
Il est plus efficace que Bellman-Ford, mais ne fonctionne que
dans le cas où toutes les valuations des arcs sont positives.
9
Principe
o On construit petit à petit, à partir de {x0}, un ensemble M de
sommets marqués. Pour tout sommet marqué, 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.
10
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) = +∞
Fin pour
Répéter
chercher x non marqué tel que d(x) = min_dist_M
marquer x
Pour tout y non marqué répéter
si d(x) + v(x, y) < d(y) alors
d(y) ← d(x) + v(x, y) (MAJ distance)
P(y) ← x (MAJ père)
min_dist_M = min{d(s), s M}
Fin pour
Jusqu’à ce que M = S
11
8 B
Exemple A
2
5
D
Origine: A 3
Destination: B
6 1
M d(A) d(B) d(C) d(D)
0 + + +
{A} - 8 6 2
C
{A,D} - DB+2=7 DC+2=3 -
(<8) (<6)
{A,D,C} - CB+3=6 - -
(<8)
{A,D,C,B} - - - -
Le chemin le plus court: A-D-C-B = 6
12
Travail à faire
1
B C
Origine: A
Destination: C 10
9
2 3 6
A
4
5
E
2
D
7
13
Solution B
1
C
10 9
2 3 6
A
4
5
E
M d(A) d(B) d(C) d(D) d(E) 2
0 + + + + D
{A}
7
10 + + 5
{A,E} 8 14 7
{A,E,D} 8 13
{A,E D, B} 9
14
Solution
1
B C
10 9
2 3 6
A
4
5
E
M d(A) d(B) d(C) d(D) d(E) 2
0 + + + + D
{A}
7
- 10 + + 5
{A,E} - 8 14 7 -
{A,E,D} - 8 13 - -
{A,E D, B} - - 9 - -
{A,E D, B,C} - - - - -
15
Exercice
Dans le contexte de la pandémie de COVID-19, un laboratoire d’analyses cherche à
optimiser la distance parcourue par l’ambulancier pour aller aux patients qui
demandent de faire des tests PCR à domicile. Les différents patients sont
géographiquement dispersés aux alentours du laboratoire. Le graphe ci-dessous
modélise cette situation tels que le nœuds « a » représente le laboratoire, le nœud
« f » est le dernier patient à visiter et les autres nœuds représentent le reste des
patients. Les routes entre les différents patients ainsi que les distances en kilomètre
sont représentées dans le graphe suivant :
16
Trouver le chemin qui minimise la distance de déplacement entre le
laboratoire et le dernier patient à visiter en appliquant l’algorithme de Dijkstra.
17
