Problème du plus
court chemin
H. Bouchriha 1
Longueur d’un arc
Soit G=(X,U) ;
u=(i,j)U l(u) ou lij appelé longueur
de l’arc u.
On dit alors que le graphe G est valué par les
longueurs l(u).
La longueur d’un chemin µ joignant le
sommet i au sommet j est donnée par :
l(µ)= l ( u)
u
H. Bouchriha 2
Problème du plus court chemin
(PCC)
Définition :
Le problème de plus court chemin entre
deux sommets i et j consiste à déterminer
un chemin de i à j, µ(i,j), de longueur
minimale.
H. Bouchriha 3
Remarque
La longueur d’un chemin comprenant un circuit
de longueur strictement négative est non
bornée (il suffit d’emprunter ce circuit une infinité
de fois)
Ce type de circuit est appelé circuit absorbant.
L’absence d’un circuit absorbant constitue une
condition nécessaire à l’existence d’un chemin
de longueur minimale.
H. Bouchriha 4
Algorithmes de
résolution
H. Bouchriha 5
Principe d’optimalité de Bellman
Théorème
Soit µ un chemin entre i et j de longueur optimale.
Toute partie µ1 de µ reliant un sommet h à un
sommet l est alors de longueur optimale.
Le chemin optimal est composé de sous-chemins
optimaux
H. Bouchriha 6
Illustration
2 3
4 5
(5) : La longueur du plus court chemin
entre 1 et 5
= min {(2) + l25 ; (3) + l35 ; (4) + l45}
H. Bouchriha 7
Quelques algorithmes de recherche
de PCC
Les algorithmes de résolution du problème de recherche
du plus court chemin seront différents suivant :
les propriétés du graphe :
graphe valué par des longueurs positives,
graphe valué par des longueurs de signes quelconques,
graphe sans circuit,
le problème considéré :
recherche du plus court chemin d’un sommet à un autre,
recherche du plus court chemin d’un sommet à tous les autres,
recherche du plus court chemin entre tous les couples de sommets.
H. Bouchriha 8
Cas d’un graphe valué par des
longueurs positives
Algorithme de Dijkstra-Moore (1959)
Recherche du plus court chemin partant d’un sommet
(noté 1) à tous les autres.
On désigne par (x) : la longueur du plus court
chemin entre le sommet 1 et le sommet x
n-1 itérations (n étant l’ordre du graphe G=(X,U))
Les sommets sont partitionnés en deux sous-ensembles
P : ensemble de sommets ayant une étiquette permanente
T = X-P : ensemble de sommets ayant une étiquette temporaire
À chaque itération un sommet est transféré de T vers P
Le calcul des plus courtes distances se fait de proche en
proche par ajustements successifs.
H. Bouchriha 9
Algorithme de Dijkstra-Moore
(1959)
Etape 1 : Initialisation
(1)=0
P={1} (P désigne le prédécesseur d’un sommet sur le
chemin)
T={2, …, N}
i T, (i)= l1i si (1,i) U
= sinon
Etape 2 :
Sélectionner j T tel que (j)= miniT (i)
Faire : T=T\{j}
P=P{j}
Si T = alors fin sinon aller à l’étape 3.
H. Bouchriha Année universitaire 2007/2008 10
Algorithme de Dijkstra-Moore
(suite)
Etape 3:
i T tel que (j,i)U
faire : (i) min ((i), (j)+ lji)
(Pricipe d’optimalité de Bellman)
Aller à l’étape 2.
H. Bouchriha 11
Exemple
Une entreprise doit distribuer
la marchandise à ses clients 4
situés aux nœuds 2 à 6. La 40 50
20
distance à parcourir d’un point 2 5
à un autre et le sens de 70 10
circulation sont indiqués dans 1 50 30
la figure ci-contre. 20
10
3 6
Déterminer les plus courts 40
chemins entre 1 et 2 et
entre 1 et 6 ?
H. Bouchriha Année universitaire 2007/2008 12
4
40 50
20
2 5
Etape 1 : Etape 2 : 70 10
(1)=0, (2)=70, (3)=10, (4)= j=6 1 50 30
(5)= (6)= P={1, 3,5,6}, T={2, 4} 20
10
P={1}, T={2, 3, 4, 5, 6} Etape 2 : 3 6
Etape 2 : 40
j=2
j=3 P={1, 3,5,6,2}, T={4}
P={1, 3}, T={2, 4, 5, 6} Etape 3 :
Etape 3 :
(4)=min{30+50,50+40} = 80/5
(2)=min{70, 10+50} = 60/3 Etape 2 :
(5)=min{, 10+20} = 30/3 j=4
(6)=min{, 10+40} = 50/3 P={1, 3,5,6,2,4}, T=
Etape 2 :
j=5 Fin de l’algorithme
P={1, 3,5}, T={2, 4, 6}
Etape 3 : Le plus court chemin de 1 à 2
(2)=min{60, 30+20}= 50/5 est 1, 3, 5, 2 de longueur 50.
(4)=min{, 30+50} = 80/5 Le plus court chemin de 1 à 6
(6)=min{50, 30+30} = 50/3 est 1, 3, 6 de longueur 50.
H. Bouchriha Année universitaire 2007/2008 13
Cas d’un graphe valué par des
longueurs de signes quelconques
Algorithme de Bellman
Graphe ayant des coûts quelconques
Recherche du plus court chemin entre un
sommet et tous les autres
Il y a convergence en absence de circuit
absorbant
Processus itératif : Déterminer le plus court chemin
de proche en proche en calculant à chaque itération
le plus court chemin à un sommet donné i en utilisant
les plus courts chemins à tous les prédécesseurs de i
H. Bouchriha Année universitaire 2007/2008 14
Algorithme de Bellman
Soit G = (X,U) un graphe d’ordre N
Etape 1 : Initialisation
m=1
(1)=0
1
j # 1 (j) = l si (1,j) U
1 1j
= + sinon
Etape 2 :
Tant que {m N-1} ou { il existe j / m+1 (j) < m (j) } Faire
Début
m+1 (j) = min (m (j) , min k#j { m (k) + lkj } )
m=m+1
Fin
Remarque : L’algorithme converge en N-1 itérations.
Si m=N et il existe j / m (j) < m-1 (j) il existe un circuit de longueur négative
(circuit absorbant)
H. Bouchriha Année universitaire 2007/2008 15
Exemple
Un agent commercial se trouvant à
la ville S décide de participer à une
foire à la ville T. Pour cela, il doit
emprunter le réseau routier donné
par la figure ci-contre. L’agent
commercial a estimé le coût de son 7
A D
transport ainsi que les bénéfices 2 -8 4 5
rapportées par la vente de produits
-5
aux différentes villes intermédiaires. S B -1 T
Sur le graphe, les dépenses ont été 3
4 1
représentées par des longueurs C E
7
positives ; les bénéfices réalisés ont 4
été représentés par des longueurs
négatives.
Trouver le chemin emprunté par
l’agent permettant de minimiser ses
coûts nets
H. Bouchriha Année universitaire 2007/2008 16
7
A D
2 -8 4 5
-5
S B -1 T
Application 4
C
1 3
E
7
4
Itération O A B C D E T
1 0/O 2/O -5/O 4/O + + +
2 0/O 2/O -6/A 4/O -1/B -2/B +
3 0/O 2/O -6/A 4/O -3/E -3/B 4/D
4 0/O 2/O -6/A 4/O -4/E -3/B 2/D
5 0/O 2/O -6/A 4/O -4/E -3/B 1/D
2(B) = Min {1(B) ; 1(A)-8 ; 1(C)+1} 3(T) = Min {2(T) ; 2(D)+5 ; 2(E)+7}
Le chemin le plus court est O A B E D T de coût = 1
H. Bouchriha Année universitaire 2007/2008 17
Cas d’un graphe sans circuit
Dans un graphe sans circuit, il existe au moins un
sommet ne possédant aucun précédent, sinon G
posséderait un circuit. Ce sommet est appelé racine du
graphe. Soit 1 ce sommet.
Dans un graphe sans circuit, il existe au moins un
sommet ne possédant aucun successeur, sinon G
posséderait un circuit.
Algorithme plus simple de recherche du plus court chemin du
sommet 1 à tous les autres
H. Bouchriha Année universitaire 2007/2008 18
Rang d’un sommet
Définition :
On définit le rang d’un sommet i d’un graphe
G sans circuit par :
rg(1) = 0,
rg(i) = le nombre d’arcs dans un chemin allant
de 1 à i, de cardinalité maximum.
H. Bouchriha Année universitaire 2007/2008 19
Rang d’un sommet
Algorithme de détermination des rangs dans un graphe
sans circuit
Etape 1 :
Initialisation : S=X, k=0
Etape 2 :
Sk={ensemble des sommets sans précédent dans S}
Pour tout i Sk, rg(i) = k
Etape 3 :
S=X-Sk
Si S= fin
Sinon
Début
Eliminer du graphe tous les arcs ayant pour origine un sommet de Sk
k=k+1,
Retour à l’étape 2
H. Bouchriha
Fin Année universitaire 2007/2008 20
Algorithme de détermination du plus court
chemin dans un graphe sans circuit
Etape 1 : Initialisation
On pose (1)=0, k=1 et S=X-{iX / rg(i)=0}
Etape 2 :
Sk={ iX / rg(i)=k}
Pour tout i Sk faire
(i)min ( (j)lji)
(j,i)U
Etape 3 :
Faire S=S- Sk
Si S= fin
Sinon faire k=k+1, retour à l’étape 2
H. Bouchriha Année universitaire 2007/2008 21
Exemple
1
2 4
3
10
1 2 5
6
4
2
3 5
7
Plus court chemin de 1 à 6 ?
rg(1) =0, rg(3)=1, rg(2)=rg(5)=2, rg(4)=3, rg(6)=4.
(1)=0, (3)=4, (2)=min (4+2, 3) =3, (5)=min (4+7)=11,
(4)=min (3+1, 11+5)=4, (6)=min (4+10, 11+2)=13.
Le plus court chemin de 1 à 6 est : 1, 3, 5 et 6.
H. Bouchriha Année universitaire 2007/2008 22
Modélisation par
PCC
H. Bouchriha 23
Stratégie de remplacement
d’équipements
Une mine a une durée totale d’exploitation de T années.
Elle utilise un équipement qu’elle a acquis à la date i=0
(équipement neuf).
- Au début de chaque année i
- Soit elle garde l’équipement en service pendant [i,i+1]
- Revendre cet équipement à un prix de récupération de v(x) avec
x est son âge et acheter un équipement neuf au prix p(i)
- Le coût d’une année de fonctionnement r(x) dépend de
son âge.
- L’équipement doit être vendu à la date T
Déterminer la politique de remplacement de l’équipement à coût
minimal
H. Bouchriha 24
Détermination d’une politique optimale
de remplacement d’équipements
0 1 2 T
Un sommet est associé à chaque date (T+1 sommets)
Un arc relie deux sommets i et j Décision d’acheter un
équipement à la date i et le vendre à j (j>i)
La longueur d’un arc = (coût d’achat + coût de fonctionnement –
prix de vente) j i
l ij p( i ) r ( s ) v ( j i )
s 1
Politique optimale de remplacement Plus court chemin de 0 à T
H. Bouchriha 25
Optimisation des achats
Le service d’achat doit assurer l’approvisionnement
pendant T périodes pour réaliser un programme de
production
Le prix d’achat p(t) dépend de la période
d’approvisionnement t.
Afin de tirer profit de la variation des prix, l’entreprise
peut :
- acheter la matière en t et constituer des stocks. Le coût
d’unitaire de stockage est h(t) en la période t.
- reporter sa demande moyennant une pénalité de retard. p est la
pénalité de reporter une unité de la demande pendant une
période
Déterminer le plan d’approvisionnement à coût minimal
H. Bouchriha 26
Détermination d’un plan d’approvisionnement
S
p(4) Politique optimale
p(1)
p(2) p(3) d’approvisionnement
Plus court chemin
1 2 3 T entre S et tous les
h(1) h(2) sommets du graphe
p p p
X = S {t, t =1,.., T} (T+1 sommets)
Un arc (S,t) correspond à la décision d’acheter en la période t. l st =
p(t)
Tout sommet t (t, t =1,.., T-1) est relié à t+1. l’arc (t,t+1) correspond
à la décision de stocker pendant la période t et a une longueur de
h(t)
Tout sommet t (t, t =2,.., T) est relié à t-1. l’arc (t,t-1) correspond à la
décision de reporter la demande de la période t à la période t-1 et a
une longueur de p.
H. Bouchriha 27
